Efficient 1-Space Bounded Hypercube Packing Algorithm
- PDF / 3,014,348 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 51 Downloads / 231 Views
Efficient 1‑Space Bounded Hypercube Packing Algorithm Paulina Grzegorek1 · Janusz Januszewski1 · Łukasz Zielonka1 Received: 24 May 2017 / Accepted: 2 May 2020 © The Author(s) 2020
Abstract A space bounded O(d∕ log d)-competitive hypercube packing algorithm with one active bin only is presented. As a starting point we give a simple 1-space bounded hypercube packing algorithm with competitive ratio (3∕2)d + O((21∕16)d ) , for d ≥ 3. Keywords Bin packing · Online algorithm · Asymptotic competitive ratio · Cube · Hypercube · One-space bounded
1 Introduction In the bin packing problem, we receive a sequence S of items of different sizes that must be packed into a finite number of bins in a way that minimizes the number of bins used. When all the items of S are accessible, the packing method is called offline. The packing method is called online, when items arrive one by one and each item has to be packed irrevocably into a bin before the next item is presented. One can consider an online method with t bins available for packing at each point in time. It is called t-space bounded. There are three types of bins: active, open and closed. At each point in time, exactly t bins are declared active. At the beginning, t bins are declared active and the remaining bins are open (there are no closed bins). Each incoming item is packed into one of the active bins; the remaining open bins are not available at this moment. We can decide to close an active bin. The most frequent reason for doing this is not enough space to pack an incoming item, however there may be other reasons based on the packing algorithm. When an active bin is * Paulina Grzegorek [email protected] Janusz Januszewski [email protected] Łukasz Zielonka [email protected] 1
Institute of Mathematics and Physics, UTP University of Science and Technology, Al. Prof. S. Kaliskiego 7, 85‑789 Bydgoszcz, Poland
13
Vol.:(0123456789)
Algorithmica
closed, a new bin from among open bins is declared active. None of the closed bins is used again. It is natural to expect a packing method to be less efficient with fewer number of active bins. An unbounded space model does not impose any limits on the number of active bins. Let S be a sequence of items, let A(S) be the number of bins used by algorithm A and let OPT(S) be the minimum possible number of bins used to pack items from S. The asymptotic competitive ratio for algorithm A is defined as: } { A(S) ∞ | OPT(S) = n . RA = lim sup sup OPT(S) n→∞ S Online bin packing is a classical problem studied for more than forty years. Onedimensional bin packing was first investigated in [27] (see also [20]), where the performance ratio of the First Fit algorithm was proved to be 17/10. The Next Fit algorithm with performance ratio not greater than 2 was discussed in [19]. Revised First Fit presented in [30] has performance ratio 5/3. The article also gives the lower bound 3/2 on the competitive ratio. The result was then improved in [3, 22] (the lower bound not smaller than 1.53635) and in [28], where the r
Data Loading...
