Minimizing flow time in cyclic schedules for identical jobs with acyclic precedence: the bottleneck lower bound

This paper studies minimizing the flow time of a cyclic schedule for repeated identical jobs, where one job is started/completed in each cycle, subject to the schedule achieving maximum throughput. We propose a branch and bound method for a single machine problem, and use this method to derive an improved lower bound for the multiple machine problem.     

Maximizing a lower bound on the computational complexity

We solve a combinatorial problem that arises in determining by a method due to Engeler lower bounds for the computational complexity of algorithmic problems. Denote by G_d the class of permutation groups G of degree d that are iterated wreath products of symmetric groups, i.e. G = S_dh?11?1S_d0 with Π^h?1_i=0d_i = d for some natural number h and some sequence (d₀,…,d_h?1) of natural numbers greater than 1. The problem is to characterize those G = S_dh?11?1S_d0 in G_d on which k(G):=log|G|/max_0≤i≤h?1log(d_i!) assumes its maximum. Our solution consists of two necessary conditions for this, namely that d₀≤d₁≤?≤d_h and that d_h is the largest prime divisor of d. Consequently, if d is a prime power, say d = p^h with p prime, then a necessary and sufficient condition is that d_i = p, 0 ≤ i ≤ h ? 1.     

On a lower bound for the perron eigenvalue

A lower boundn ^–1 _i,k a_ik for the Perron eigenvalue of a symmetric non-negative irreducible matrixA=(a _ik) is studied and compared with certain other lower bounds.     

On a lower bound of commutativity degree

The commutativity degree of a finite group G, denoted by Pr(G), is the probability that a randomly chosen pair of elements of G commute. The object of this paper is to derive a lower bound for Pr(G) and study some of its consequences towards characterizing G.     

A lower bound for the circumference of a graph

Let G=(V, E) be a block of order n, different from K_n. Let m=min {d(x)+d(y): [x, y]?E}. We show that if m?n then G contains a cycle of length at least m.     

A lower bound for the interval number of a graph

The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I₁,…,I_n with every I_i being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number.     

A lower bound for the spectral radius of a digraph

We show that the spectral radius ρ(D) of a digraph D with n vertices and c₂ closed walks of length 2 satisfies Moreover, equality occurs if and only if D is the symmetric digraph associated to a -regular graph, plus some arcs that do not belong to cycles. As an application of this result, we construct new sharp upper bounds for the low energy of a digraph, which extends Koolen and Moulton bounds of the energy to digraphs.     

A lower bound for the distortion of a knotted curve

It is proved that the distortion of any knotted curve in ℝ³ is greater than 4.76. This improves the result by John M. Sullivan and Elizabeth. Denne. Bibliography: 3 titles.     

A matrix lower bound

Four essentially different interpretations of a lower bound for linear operators are shown to be equivalent for matrices (involving inequalities, convex sets, minimax problems, and quotient spaces). Properties stated by von Neumann in a restricted case are satisfied by the lower bound. Applications are made to rank reduction, s-numbers, condition numbers, and pseudospectra. In particular, the matrix lower bound is the distance to the nearest matrix with strictly contained row or column spaces, and it occurs in a condition number formula for any consistent system of linear equations, including those that are underdetermined.     

On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems

New observations are made about two lower bound schemes for single-machine min-sum scheduling problems. We find that the strongest bound of those provided by transportation problem relaxations can be computed by solving a linear program. We show the equivalence of this strongest bound and the bound provided by the LP relaxation of the time-indexed integer programming formulation. These observations lead to a new lower bound scheme that yields fast approximation of the time-indexed bound. Several techniques are developed to facilitate the effective use of the new lower bound in branch-and-bound. Numerical experiments are conducted on 375 benchmark problems of the total weighted tardiness problem from OR-Library. Results obtained with our new method are spectacular; we are able to solve all 125 open problems to optimality.     

Volume collapsed three-manifolds with a lower curvature bound

In this paper we determine the topology of three-dimensional complete orientable Riemannian manifolds with a uniform lower bound of sectional curvature whose volume is sufficiently small.     

A lower bound for the volume of a four-dimensional closed manifold

A closed orientable four-dimensional manifoldM ⁴, whose sectional curvatures satisfy –1 K 1, is considered. If the product of the curvatures of orthogonal area elements is nonnegative and if at least at one point all the curvatures are different from zero, then the estimate vol(M ⁴) > (4/9)² is obtained for the volume ofM ⁴. A theorem on the local structure of a manifold with small volume whose curvatures at every point are of the same sign is established.Translated from Ukrainskii Geometricheskii Sbornik, No. 34, pp. 3–8, 1991.     

A lower bound for the smallest singular value of a matrix

For a matrix A which is diagonally dominant both by rows and by columns, we give bounds for 6A^-16₁ and 6A^-16_∞, which then can be used to give a lower bound for the smallest singular value. We also show that these bounds can be attained, and show how the result can be extended to block matrices.     

Approximation of holomorphic maps with a lower bound on the rank

Let be a closed polydisc or ball in , and let be a quasi-projective algebraic manifold which is Zariski locally equivalent to , or a complement of an algebraic subvariety of codimension in such a manifold. If is an integer satisfying , then every holomorphic map from a neighborhood of to with rank at every point of can be approximated uniformly on by entire maps with rank at every point of .