Computing the asymptotic worst-case of bin packing lower bounds

This paper addresses the issue of computing the asymptotic worst-case of lower bounds for the Bin Packing Problem. We introduce a general result that allows to bound the asymptotic worst-case performance of any lower bound for the problem and to derive for the first time the asymptotic worst-case of the well-known bound L₃ by Martello and Toth. We also show that the general result allows to easily derive the asymptotic worst-case of several lower bounds proposed in the literature.     

Lattice Algorithms for Multivariate L ∞ Approximation in the Worst-Case Setting

We approximate d-variate functions from weighted Korobov spaces with the error of approximation defined in the L _∞ sense. We study lattice algorithms and consider the worst-case setting in which the error is defined by its worst-case behavior over the unit ball of the space of functions. A lattice algorithm is specified by a generating (integer) vector. We propose three choices of such vectors, each corresponding to a different search criterion in the component-by-component construction. We present worst-case error bounds that go to zero polynomially with n ^?1, where n is the number of function values used by the lattice algorithm. Under some assumptions on the weights of the function space, the worst-case error bounds are also polynomial in d, in which case we have (polynomial) tractability, or even independent of d, in which case we have strong (polynomial) tractability. We discuss the exponents of n ^?1 and stress that we do not know if these exponents can be improved.     

Worst-case analysis of demand point aggregation for the Euclidean p-median problem

Solving large-scale p-median problems is usually time consuming. People often aggregate the demand points in a large-scale p-median problem to reduce its problem size and make it easier to solve. Most traditional research on demand point aggregation is either experimental or assuming uniformly distributed demand points in analytical studies. In this paper, we study demand point aggregation for planar p-median problem when demand points are arbitrarily distributed. Efficient demand aggregation approaches are proposed with the corresponding attainable worst-case aggregation error bounds measured. We demonstrate that these demand aggregation approaches introduce smaller worst-case aggregation error bounds than that of the honeycomb heuristic [Papadimitriou, C.H., 1981. Worst-case and probabilistic analysis of a geometric location problem. SIAM Journal on Computing 10, 542–557] when demand points are arbitrarily distributed. We also conduct numerical experiments to show their effectiveness.     

Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint

We study the problem of scheduling n non-preemptable jobs on a single machine which is not available for processing during a given time period. The objective is to minimize the sum of the job completion times. The best known approximation algorithm for this NP-hard problem has a relative worst-case error bound of 17.6%. We present a parametric O(nlog n)-algorithm H with which better worst-case error bounds can be obtained. The best error bound calculated for the algorithm in the paper is 7.4%. In a computational experiment, we test the algorithm with the performance guarantee set to 10.2%. It turns out that randomly generated instances with up to 1000 jobs can be solved with a mean (maximum) error of 0.31% (3.18%) and a mean (maximum) computation time of 0.8 (9.7) seconds.     

Bounds for solid angles of lattices of rank three

We find sharp absolute constants C₁ and C₂ with the following property: every well-rounded lattice of rank 3 in a Euclidean space has a minimal basis so that the solid angle spanned by these basis vectors lies in the interval [C₁,C₂]. In fact, we show that these absolute bounds hold for a larger class of lattices than just well-rounded, and the upper bound holds for all. We state a technical condition on the lattice that may prevent it from satisfying the absolute lower bound on the solid angle, in which case we derive a lower bound in terms of the ratios of successive minima of the lattice. We use this result to show that among all spherical triangles on the unit sphere in RN with vertices on the minimal vectors of a lattice, the smallest possible area is achieved by a configuration of minimal vectors of the (normalized) face centered cubic lattice in R³. Such spherical configurations come up in connection with the kissing number problem.     

A note on “scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan”

In a recent paper, Chen [J.S. Chen, Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, European Journal of Operational Research 190 (2008) 90–102] proposes a heuristic algorithm to deal with the problem Scheduling of Nonresumable Jobs and Flexible Maintenance Activities on A Single Machine to Minimize Makespan  . Chen also provides computational results to demonstrate its effectiveness. In this note, we first show that the worst-case performance bound of this heuristic algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case performance bound less than 2 unless P=NP$P=\mathit{NP}$, which implies that Chen’s heuristic algorithm is the best possible polynomial time approximation algorithm for the considered scheduling problem.     

QMC Rules of Arbitrary High Order: Reproducing Kernel Hilbert Space Approach

In this paper we consider numerical integration of smooth functions lying in a particular reproducing kernel Hilbert space. We show that the worst-case error of numerical integration in this space converges at the optimal rate, up to some power of a log?N factor. A similar result is shown for the mean square worst-case error, where the bound for the latter is always better than the bound for the square worst-case error. Finally, bounds for integration errors of functions lying in the reproducing kernel Hilbert space are given. The paper concludes by illustrating the theory with numerical results.     

Sharp convergence rates for averaged nonexpansive maps

We establish sharp estimates for the convergence rate of the Kranosel’ski?–Mann fixed point iteration in general normed spaces, and we use them to show that the optimal constant of asymptotic regularity is exactly \(1/\sqrt \pi \). To this end we consider a nested family of optimal transport problems that provide a recursive bound for the distance between the iterates. We show that these bounds are tight by building a nonexpansive map T: [0, 1]^N → [0, 1]^N that attains them with equality, settling a conjecture by Baillon and Bruck. The recursive bounds are in turn reinterpreted as absorption probabilities for an underlying Markov chain which is used to establish the tightness of the constant \(1/\sqrt \pi \).     

Lower Bounds for Shellsort

We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an Ω(n (lg² n)/(lg lg n)²) lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time of Shellsort algorithms, again for arbitrary increment sequences. Our lower bounds establish an almost tight trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence.     

Density of the circular chromatic numbers of series‐parallel graphs

In this paper we show that every simple cubic graph on n vertices has a set of at least ? n/4 ? disjoint 2‐edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a set in a simple cubic graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 57–79, 2003     

Optimal designs for weighted approximation and integration of stochastic processes on [0,∞)

We study minimal errors and optimal designs for weighted L₂-approximation and weighted integration of Gaussian stochastic processes X defined on the half-line [0,∞). Under some regularity conditions, we obtain sharp bounds for the minimal errors for approximation and upper bounds for the minimal errors for integration. The upper bounds are proven constructively for approximation and non-constructively for integration. For integration of the r-fold integrated Brownian motion, the upper bound is proven constructively and we have a matching lower bound.     

Performance of first-order methods for smooth convex minimization: a novel approach

We introduce a novel approach for analyzing the worst-case performance of first-order black-box optimization methods. We focus on smooth unconstrained convex minimization over the Euclidean space. Our approach relies on the observation that by definition, the worst-case behavior of a black-box optimization method is by itself an optimization problem, which we call the performance estimation problem (PEP). We formulate and analyze the PEP for two classes of first-order algorithms. We first apply this approach on the classical gradient method and derive a new and tight analytical bound on its performance. We then consider a broader class of first-order black-box methods, which among others, include the so-called heavy-ball method and the fast gradient schemes. We show that for this broader class, it is possible to derive new bounds on the performance of these methods by solving an adequately relaxed convex semidefinite PEP. Finally, we show an efficient procedure for finding optimal step sizes which results in a first-order black-box method that achieves best worst-case performance.     

The maximum cut problem on blow-ups of multiprojective spaces

The maximum cut problem for a quintic del Pezzo surface Bl₄(?²) asks: Among all partitions of the 10 exceptional curves into two disjoint sets, what is the largest possible number of pairwise intersections? In this article we show that the answer is 12. More generally, we obtain bounds for the maximum cut problem for the minuscule varieties X _a,b,c :=Bl _b+c ((? ^c?1) ^a?1) studied by Mukai and Castravet-Tevelev and show that these bounds are asymptotically sharp for infinite families and exact in some cases. The key to our results is the fact that certain natural embeddings of the classes of (?1)-divisors on these varieties are optimal for the semidefinite relaxation of the maximum cut problem on graphs proposed by Goemans and Williamson. These results are a new optimality property of Weyl orbits of root systems of type A,D and E. Motivated by our results on the varieties X _a,b,c we show that the Goemans–Williamson maxcut stochastic approximation algorithm has provably optimal asymptotic performance in symmetric strongly regular graphs of bounded spectra, in marked contrast with its worst-case behavior.     

Sharp weighted bounds without testing or extrapolation

We give a short proof of the sharp weighted bound for sparse operators that holds for all p,1?<?p?< ??. By recent developments this implies the bounds hold for any Calderón?CZygmund operator. The novelty of our approach is that we avoid two techniques that are present in other proofs: two weight inequalities and extrapolation. Our techniques are applicable to fractional integral operators as well.     

Error bounds for linear complementarity problems of DB-matrices

Doubly B-matrices (DB-matrices), which properly contain B-matrices, are introduced by Peña (2003) [2]. In this paper we present error bounds for the linear complementarity problem when the matrix involved is a DB-matrix and a new bound for linear complementarity problem of a B-matrix. The numerical examples show that the bounds are sharp.     

A note on makespan minimization in two-stage flexible flow shops with uniform machines

We consider the two-stage flexible flow shop makespan minimization problem with uniform parallel machines. Soewandi and Elmaghraby [Soewandi, H., Elmaghraby, S., 2003. Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan. IIE Transaction 35, 467–477] developed a heuristic (S–E) and derived a machine speed-dependent worst-case ratio bound for it. We point out that this bound works well when the uniform machines have approximately equal speeds but is not indicative of the performance of the S–E heuristic when the machine speeds are in a wide range. Motivated by this observation, we propose an alternative tight machine-speed dependent worst-case bound for the S–E heuristic that works well when the machine speeds vary significantly. We then combine the two speed-dependent ratio bounds into a speed-independent bound. Our findings facilitate the narrowing of the gap between experimental performance and worst-case bound for the S–E heuristic.     

Edge search in graphs with restricted test sets

Suppose a graph G(V,E) contains one defective edge e. We search for the endpoints of e by asking questions of the form “Is at least one of the vertices of X an endpoint of e?”, where X is a subset of V with cardinality at most p. Then what is the minimum number c_p(G) of questions, which are needed in the worst case to find e?We solve this search problem suggested by M. Aigner in [M. Aigner, Combinatorial Search, Teubner, 1988] by deriving lower and sharp upper bounds for c_p(G). For the case that G is the complete graph K_n the problem described above is equivalent to the (2,n) group testing problem with test sets of cardinality at most p. We present sharp upper and lower bounds for the worst case number c_p of tests for this group testing problem and show that the maximum difference between the upper and the lower bounds is 3.     

Random weights, robust lattice rules and the geometry of the cbcrc algorithm

In this paper we study lattice rules which are cubature formulae to approximate integrands over the unit cube [0,1] ^s from a weighted reproducing kernel Hilbert space. We assume that the weights are independent random variables with a given mean and variance for two reasons stemming from practical applications: (i) It is usually not known in practice how to choose the weights. Thus by assuming that the weights are random variables, we obtain robust constructions (with respect to the weights) of lattice rules. This, to some extend, removes the necessity to carefully choose the weights. (ii) In practice it is convenient to use the same lattice rule for many different integrands. The best choice of weights for each integrand may vary to some degree, hence considering the weights random variables does justice to how lattice rules are used in applications. In this paper the worst-case error is therefore a random variable depending on random weights. We show how one can construct lattice rules which perform well for weights taken from a set with large measure. Such lattice rules are therefore robust with respect to certain changes in the weights. The construction algorithm uses the component-by-component (cbc) idea based on two criteria, one using the mean of the worst case error and the second criterion using a bound on the variance of the worst-case error. We call the new algorithm the cbc2c (component-by-component with 2 constraints) algorithm. We also study a generalized version which uses r constraints which we call the cbcrc (component-by-component with r constraints) algorithm. We show that lattice rules generated by the cbcrc algorithm simultaneously work well for all weights in a subspace spanned by the chosen weights ?? ⁽¹⁾, . . . , ?? ^(r). Thus, in applications, instead of finding one set of weights, it is enough to find a convex polytope in which the optimal weights lie. The price for this method is a factor r in the upper bound on the error and in the construction cost of the lattice rule. Thus the burden of determining one set of weights very precisely can be shifted to the construction of good lattice rules. Numerical results indicate the benefit of using the cbc2c algorithm for certain choices of weights.     

Sharp bounds for integral means

We introduce a bound M of f, ‖f‖_∞?M?2‖f‖_∞, which allows us to give for 0?p<∞ sharp upper bounds, and for −∞<p<0 sharp lower bounds for the average of |f|^p over E if the average of f over E is zero. As an application we give a new proof of Grüss's inequality estimating the covariance of two random variables. We also give a new estimate for the error term in the trapezoidal rule.     

New Bounds for Perfect Hashing via Information Theory

A set of sequences of length t from a b-element alphabet is called k-separated if for every k-tuple of the sequences there exists a coordinate in which they all differ. The problem of finding, for fixed t, b, and k, the largest size N(t, b, k) of a k-separated set of sequences is equivalent to finding the minimum size of a (b, k)-family of perfect hash functions for a set of a given size. We shall improve the bounds for N(t, b, k) obtained by Fredman and Komlós [1].Körner [2] has shown that the proof in [1] can be reduced to an application of the sub-additivity of graph entropy [3]. He also pointed out that this sub-additivity yields a method to prove non-existence bounds for graph covering problems. Our new non-existence bound is based on an extension of graph entropy to hypergraphs.