Start of Main Content
Journal Article
Probabilistic Analysis of a Heuristic for the Dual Bin Packing Problem
Information Processing Letters
Author(s)
In this paper we study the probabilistic behavior of the first fit increasing heuristics for the dual bin packing problem. In this problem we seek to maximize the number of items that can be packed into m unit capacity bins. We show that when the items to be packed are independent and identically distributed, then the relative error of first fit increasing tends to zero in probability as the number of items tends to infinity. We also consider an on-line variant of this problem and propose a simple heuristics whose relative error tends to zero in probability as the number of items tends to infinity under the assumption that the item sizes are independently and identically distributed according to a distribution with finite mean and with zero in its compact support.
Date Published:
1989
Citations:
Foster, Dean, Rakesh Vohra. 1989. Probabilistic Analysis of a Heuristic for the Dual Bin Packing Problem. Information Processing Letters. (6)287-290.