Dynamic multi-dimensional bin packing

A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced by Coffman et al. (1983) [7]. In this formulation, items arrive and depart and the objective is to minimize the maximal number of bins ever used over all times. We study the oriented multi-dimensional dynamic bin packing problem for two dimensions, three dimensions and multiple dimensions. Specifically, we consider dynamic packing of squares and rectangles into unit squares and dynamic packing of three-dimensional cubes and boxes into unit cubes. We also study dynamic d-dimensional hypercube and hyperbox packing. For dynamic d-dimensional box packing we define and analyze the algorithm NFDH for the offline problem and present a dynamic version. This algorithm was studied before for rectangle packing and for square packing and was generalized only for multi-dimensional cubes. We present upper and lower bounds for each of these cases.     

New classes of fast lower bounds for bin packing problems

The bin packing problem is one of the classical NP-hard optimization problems. In this paper, we present a simple generic approach for obtaining new fast lower bounds, based on dual feasible functions. Worst-case analysis as well as computational results show that one of our classes clearly outperforms the previous best “economical” lower bound for the bin packing problem by Martello and Toth, which can be understood as a special case. In particular, we prove an asymptotic worst-case performance of 3/4 for a bound that can be computed in linear time for items sorted by size. In addition, our approach provides a general framework for establishing new bounds. Received: August 11, 1998 / Accepted: February 1, 2001?Published online September 17, 2001     

On fractional moments of Dirichlet <Emphasis Type="Italic">L</Emphasis>-functions,II

We obtain upper and lower bounds for fractional moments of Dirichlet L-functions. Published in Lietuvos Matematikos Rinkinys, Vol. 46, No. 4, pp. 606–621, October–December, 2006.     

On the effectiveness of the Harmonic Shelf Algorithm for on-line strip packing

In [J. Csirik, G.J. Woeginger, An on-line algorithm for multidimensional bin packing, Inform. Process. Lett. 63 (1997) 171-175] the authors study the asymptotic worst case ratio between the height of the strip needed to on-line pack a list of boxes by means of the Harmonic Shelf Algorithm and the height of the strip used by an optimal algorithm. In this note we analyze the effectiveness of the former algorithm in terms of the ratio between the unused area inside the strip and the total size of this strip, and we show that the Harmonic Shelf Algorithm is also capable of packing items so that the asymptotic worst case value of this ratio comes arbitrarily close to .     

The average-case analysis of some on-line algorithms for bin packing

In this paper we give tighter bounds than were previously known for the performance of the bin packing algorithms Best Fit and First Fit when the inputs are uniformly distributed on [0, 1]. We also give a general lower bound for the performance of any on-line bin packing algorithm on this distribution. We prove these results by analyzing optimal matchings on points randomly distributed in a unit square. We give a new lower bound for the up-right matching problem. A preliminary version of this paper appeared inProc. 25th IEEE Symposium on Foundations of Computer Science, 193–200. This research was done while the author was at the Massachusetts Institute of Technology Dept. of Mathematics and was supported by a NSF Graduate Fellowship and by Air Force grant OSR-82-0326.     

New upper bounds for online strip packing

In this paper, we consider the online strip packing problem, in which a list of online rectangles has to be packed without overlap or rotation into one or more strips of width 1 and infinite height so as to minimize the required height of the packing. By analyzing a two-phase shelf algorithm, we derive a new upper bound 6.4786 on the competitive ratio for online one strip packing. This result improves the best known upper bound of 6.6623. We also extend this algorithm to online multiple strips packing and present some numeric upper bounds on their competitive ratios which are better than the previous bounds.     

Improved lower bounds for the online bin stretching problem

We use game theory techniques to automatically compute improved lower bounds on the competitive ratio for the bin stretching problem. Using these techniques, we improve the best lower bound for this problem to 19/14. We explain the technique and show that it can be generalized to compute lower bounds for any online or semi-online packing or scheduling problem.     

Upper bounds for Gaussian stochastic programs

We present a construction which gives deterministic upper bounds for stochastic programs in which the randomness appears on the right–hand–side and has a multivariate Gaussian distribution. Computation of these bounds requires the solution of only as many linear programs as the problem has variables. Received December 2, 1997 / Revised version received January 5, 1999? Published online May 12, 1999     

Sigma–delta quantization errors and the traveling salesman problem

In transmission, storaging and coding of digital signals we frequently perform A/D conversion using quantization. In this paper we study the maximal and mean square errors as a result of quantization. We focus on the sigma–delta modulation quantization scheme in the finite frame expansion setting. We show that this problem is related to the classical Traveling Salesman Problem (TSP) in the Euclidean space. It is known [Benedetto et al., Sigma–delta () quantization and finite frames, IEEE Trans. Inform. Theory 52, 1990–2005 (2006)] that the error bounds from the sigma–delta scheme depends on the ordering of the frame elements. By examining a priori bounds for the Euclidean TSP we show that error bounds in the sigma–delta scheme is superior to those from the pulse code modulation (PCM) scheme in general. We also give a recursive algorithm for finding an ordering of the frame elements that will lead to good maximal error and mean square error. Supported in part by the National Science Foundation grant DMS-0139261.     

New lower bounds for the three-dimensional orthogonal bin packing problem

In this paper, we consider the three-dimensional orthogonal bin packing problem, which is a generalization of the well-known bin packing problem. We present new lower bounds for the problem from a combinatorial point of view and demonstrate that they theoretically dominate all previous results from the literature. The comparison is also done concerning asymptotic worst-case performance ratios. The new lower bounds can be more efficiently computed in polynomial time. In addition, we study the non-oriented model, which allows items to be rotated.     

Tight bounds for minimax grid matching with applications to the average case analysis of algorithms

The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms. The problem has arisen in a number of interesting and seemingly unrelated areas, including wafer-scale integration of systolic arrays, two-dimensional discrepancy problems, and testing pseudorandom number generators. However, the minimax grid matching problem is best known for its application to the maximum up-right matching problem. The maximum up-right matching problem was originally defined by Karp, Luby and Marchetti-Spaccamela in association with algorithms for 2-dimensional bin packing. More recently, the up-right matching problem has arisen in the average case analysis of on-line algorithms for 1-dimen-sional bin packing and dynamic allocation.In this paper, we solve both the minimax grid matching problem and the maximum up-right matching problem. As a direct result, we obtain tight upper bounds on the average case behavior of the best algorithms known for 2-dimensional bin packing, 1-dimensional on-line bin packing and on-line dynamic allocation. The results also solve a long-open question in mathematical statistics.This research was supported by Air Force Contracts AFOSR-82-0326 and AFOSR-86-0078, NSF Grant 8120790, and DARPA contract N00014-80-C-0326. In addition, Tom Leighton was supported by an NSF Presidential Young Investigator Award with matching funds from Xerox and IBM.     

Perturbation bounds for polynomials

Using two different elementary approaches we derive a global and a local perturbation theorem on polynomial zeros that significantly improve the results of Ostrowski (Acta Math 72:99–257, 1940), Elsner et al. (Linear Algebra Appl 142:195–209, 1990). A comparison of different perturbation bounds shows that our results are better in many cases than the similar local result of Beauzamy (Can Math Bull 42(1):3–12, 1999). Using the matrix theoretical approach we also improve the backward stability result of Edelman and Murakami (Proceedings of the Fifth SIAM Conference on Applied Linear Algebra, SIAM, Philapdelphia, 1994; Math Comput 64:210–763, 1995).     

New lower bounds for the three-dimensional finite bin packing problem

The three-dimensional finite bin packing problem (3BP) consists of determining the minimum number of large identical three-dimensional rectangular boxes, bins, that are required for allocating without overlapping a given set of three-dimensional rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. We propose new lower bounds for the problem where the items have a fixed orientation and then we extend these bounds to the more general problem where for each item the subset of rotations by 90° allowed is specified. The proposed lower bounds have been evaluated on different test problems derived from the literature. Computational results show the effectiveness of the new lower bounds.     

A new destructive bounding scheme for the bin packing problem

In this paper, we present a new lower bounding scheme for the one-dimensional bin packing problem based on a destructive approach and we prove its effectiveness to solve hard instances. Performance comparison to other available lower bounds shows the effectiveness of our proposed lower bounds.     

Local behavior of an iterative framework for generalized equations with nonisolated solutions

 An iterative framework for solving generalized equations with nonisolated solutions is presented. For generalized equations with the structure , where is a multifunction and F is single-valued, the framework covers methods that, at each step, solve subproblems of the type . The multifunction approximates F around s. Besides a condition on the quality of this approximation, two other basic assumptions are employed to show Q-superlinear or Q-quadratic convergence of the iterates to a solution. A key assumption is the upper Lipschitz-continuity of the solution set map of the perturbed generalized equation . Moreover, the solvability of the subproblems is required. Conditions that ensure these assumptions are discussed in general and by means of several applications. They include monotone mixed complementarity problems, Karush-Kuhn-Tucker systems arising from nonlinear programs, and nonlinear equations. Particular results deal with error bounds and upper Lipschitz-continuity properties for these problems. Received: November 2001 / Accepted: November 2002 Published online: December 9, 2002 Key Words. generalized equation – nonisolated solutions – Newton's method – superlinear convergence – upper Lipschitz-continuity – mixed complementarity problem – error bounds Mathematics Subject Classification (1991): 90C30, 65K05, 90C31, 90C33     

Provable bounds for the mean queue lengths in a heterogeneous priority queue

We analyze a two-class two-server system with nonpreemptive heterogeneous priority structures. We use matrix–geometric techniques to determine the stationary queue length distributions. Numerical solution of the matrix–geometric model requires that the number of phases be truncated and it is shown how this affects the accuracy of the results. We then establish and prove upper and lower bounds for the mean queue lengths under the assumption that the classes have equal mean service times. This revised version was published online in June 2006 with corrections to the Cover Date.     

The condition number of real Vandermonde, Krylov and positive definite Hankel matrices

Summary. We show that the Euclidean condition number of any positive definite Hankel matrix of order may be bounded from below by with , and that this bound may be improved at most by a factor . Similar estimates are given for the class of real Vandermonde matrices, the class of row-scaled real Vandermonde matrices, and the class of Krylov matrices with Hermitian argument. Improved bounds are derived for the case where the abscissae or eigenvalues are included in a given real interval. Our findings confirm that all such matrices – including for instance the famous Hilbert matrix – are ill-conditioned already for “moderate” order. As application, we describe implications of our results for the numerical condition of various tasks in Numerical Analysis such as polynomial and rational i nterpolation at real nodes, determination of real roots of polynomials, computation of coefficients of orthogonal polynomials, or the iterative solution of linear systems of equations. Received December 1, 1997 / Revised version received February 25, 1999 / Published online 16 March 2000     

On-line bin packing — A restricted survey

In the classical bin packing problem, one is asked to pack items of various sizes into the minimum number of equal-sized bins. In the on-line version of this problem, the packer is given the items one by one and must immediately and irrevocably assign every item to its bin, without knowing the future items. Beginning with the first results in the early 1970's, we survey — from the worst case point of view — the approximation results obtained for on-line bin packing, higher dimensional versions of the problem, lower bounds on worst case ratios and related results.This work was partially supported by the Christian Doppier Laboratorium für Diskrete Optimierung.