Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Bin Packing with Rejection Revisited

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We consider the following generalization of bin packing. Each item has a size in (0,1] associated with it, as well as a rejection cost, that an algorithm must pay if it chooses not to pack this item. The cost of an algorithm is the sum of all rejection costs of rejected items plus the number of unit sized bins used for packing all other items.

We first study the offline version of the problem and design an APTAS for it. This is a non-trivial generalization of the APTAS given by Fernandez de la Vega and Lueker for the standard bin packing problem. We further give an approximation algorithm of an absolute approximation ratio 3/2, where this value is best possible unless P=NP.

Finally, we study an online version of the problem. For the bounded space variant, where only a constant number of bins can be open simultaneously, we design a sequence of algorithms whose competitive ratios tend to the best possible asymptotic competitive ratio. These algorithms are generalizations of bounded space algorithms for standard bin packing. We show that our algorithms have the same asymptotic competitive ratios as these known for the standard problem, for which the sequence of the competitive ratios tends to Π∞≈1.691. Furthermore, we introduce an unbounded space algorithm which achieves a much smaller asymptotic competitive ratio. All our results improve upon previous results of Dósa and He.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bansal, N., Blum, A., Chawla, S., Dhamdhere, K.: Scheduling for flow-time with admission control. In: Proc. of the 11th Annual European Symposium on Algorithms (ESA2003), pp. 43–54 (2003)

  2. Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., Stougie, L.: Multiprocessor scheduling with rejection. SIAM J. Discrete Math. 13(1), 64–78 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bein, W.W., Correa, J.R., Han, X.: A fast asymptotic approximation scheme for bin packing with rejection. In: Proc. of the 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE2007), pp. 209–218 (2007)

  4. Caprara, A., Kellerer, H., Pferschy, U.: Approximation schemes for ordered vector packing problems. Naval Res. Logist. 92, 58–69 (2003)

    Article  MathSciNet  Google Scholar 

  5. Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D. (ed.) Approximation Algorithms. PWS Publishing Company, Boston (1997)

    Google Scholar 

  6. Csirik, J., Woeginger, G.J.: On-line packing and covering problems. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms: The State of the Art, pp. 147–177 (1998)

  7. Csirik, J., Woeginger, G.J.: Resource augmentation for online bounded space bin packing. J. Algorithms 44(2), 308–320 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  8. Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1+ε in linear time. Combinatorica 1, 349–355 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  9. Dósa, G.: The tight bound of first fit decreasing bin-packing algorithm is FFD(I)≤11/9OPT(I)+6/9. In: Proc. of the 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE2007), pp. 1–11 (2007)

  10. Dósa, G., He, Y.: Bin packing problems with rejection penalties and their dual problems. Inf. Comput. 204(5), 795–815 (2006)

    Article  MATH  Google Scholar 

  11. Engels, D.W., Karger, D.R., Kolliopoulos, S.G., Sengupta, S., Uma, R.N., Wein, J.: Techniques for scheduling with rejection. J. Algorithms 49(1), 175–191 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  12. Epstein, L., Levin, A.: AFPTAS results for common variants of bin packing: a new method to handle the small items. Manuscript (2007)

  13. Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, New York (1979)

    MATH  Google Scholar 

  14. Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34(1), 144–162 (1987)

    MathSciNet  Google Scholar 

  15. Hoogeveen, H., Skutella, M., Woeginger, G.J.: Preemptive scheduling with rejection. In: Proc. of the 8th Annual European Symposium on Algorithms (ESA2000), pp. 268–277 (2000)

  16. Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8, 272–314 (1974)

    MATH  Google Scholar 

  17. Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 256–278 (1974)

    Article  MathSciNet  Google Scholar 

  18. Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS’82), pp. 312–320 (1982)

  19. Lee, C.C., Lee, D.T.: A simple online bin packing algorithm. J. ACM 32(3), 562–572 (1985)

    MATH  Google Scholar 

  20. Ramanan, P., Brown, D.J., Lee, C.C., Lee, D.T.: Online bin packing in linear time. J. Algorithms 10, 305–326 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  21. Seiden, S.S.: On the online bin packing problem. J. ACM 49(5), 640–671 (2002)

    MathSciNet  Google Scholar 

  22. Simchi-Levi, D.: New worst-case results for the bin-packing problem. Naval Res. Logist. 41(4), 579–585 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  23. Ullman, J.D.: The performance of a memory allocation algorithm. Technical Report 100, Princeton University, Princeton, NJ (1971)

  24. van Vliet, A.: An improved lower bound for online bin packing algorithms. Inf. Process. Lett. 43(5), 277–284 (1992)

    Article  MATH  Google Scholar 

  25. Yao, A.C.C.: New algorithms for bin packing. J. ACM 27, 207–227 (1980)

    MATH  Google Scholar 

  26. Yue, M.: A simple proof of the inequality FFD(L)≤(11/9)OPT(L)+1, ∀ L, for the FFD bin-packing algorithm. Acta Math. Appl. Sin. 7, 321–331 (1991)

    Article  MATH  Google Scholar 

  27. Zhang, G.: Private communication

  28. Zhang, G., Cai, X., Wong, C.K.: Linear time approximation algorithms for bin packing. Oper. Res. Lett. 26, 217–222 (2000)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Haifa, 31905, Haifa, Israel

    Leah Epstein

Authors
  1. Leah Epstein
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Leah Epstein.

Additional information

An extended abstract of this paper will appear in the Proceedings of the 4th Workshop on Approximation and Online Algorithms (WAOA 2006).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Epstein, L. Bin Packing with Rejection Revisited. Algorithmica 56, 505–528 (2010). https://doi.org/10.1007/s00453-008-9188-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-008-9188-9

Keywords

Search

Navigation