Loading...
Please wait, while we are loading the content...
Similar Documents
Optimal Online Algorithms for Multidimensional Packing Problems (2005)
| Content Provider | CiteSeerX |
|---|---|
| Author | Epstein, Leah Stee, Rob Van |
| Abstract | We solve an open problem in the literature by providing an online algorithm for multidimensional bin packing that uses only bounded space. To achieve this, we introduce a new technique for classifying the items to be packed. We show that our algorithm is optimal among bounded space algorithms for any dimension d> 1. Its asymptotic performance ratio is (Π∞) d, where Π ∞ ≈ 1.691 is the asymptotic performance ratio of the one-dimensional algorithm Harmonic. A modified version of this algorithm for the case where all items are hypercubes is also shown to be optimal. Its asymptotic performance ratio is sublinear in d. Furthermore, we extend the techniques used in these algorithms to give optimal algorithms for online bounded space variable-sized packing and resource augmented packing. |
| File Format | |
| Volume Number | 35 |
| Journal | SIAM J. COMPUTING |
| Language | English |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Optimal Online Algorithm Multidimensional Packing Problem Asymptotic Performance Ratio Bounded Space New Technique Modified Version Optimal Algorithm Open Problem One-dimensional Algorithm Harmonic Multidimensional Bin Packing Space Variable-sized Packing Bounded Space Algorithm Online Algorithm |
| Content Type | Text |
| Resource Type | Article |
