Probabilistic analysis of a generalized bin packing problem and applications

Probabilistic analysis of a generalized bin packing problem and applications

0.00 Avg rating0 Votes
Article ID: iaor20003750
Country: United States
Volume: 45
Issue: 4
Start Page Number: 596
End Page Number: 609
Publication Date: Jul 1997
Journal: Operations Research
Authors: ,
Keywords: bin packing
Abstract:

We give a unified probabilistic analysis for a general class of bin packing problems by directly analyzing corresponding mathematical programs. In this general class of packing problems, objects are described by a given number of attribute values. (Some attributes may be discrete; others may be continuous.) Bins are sets of objects, and the collection of feasible bins is merely required to satisfy some general consistency properties. We characterize the asymptotic optimal value as the value of an easily specified linear program whose size is independent of the number of objects to be packed, or as the limit of a sequence of such linear program values. We also provide bounds for the rate of convergence of the average cost to its asymptotic value. The analysis suggests an (almost surely) asymptotically E-optimal heuristic that runs in linear time. The heuristics can be designed to be asymptotically optimal while still running in polynomial time. We also show that in several important cases, the algorithm has both polynomially fast convergence and polynomial running time. This heuristic consists of solving a linear program and rounding its solution up to the nearest integer vector. We show how our results can be used to analyze a general vehicle routing model with capacity and time window constraints.

Reviews

Required fields are marked *. Your email address will not be published.