Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Approximation Schemes for Packing with Item Fragmentation

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 3879))

Included in the following conference series:

Abstract

We consider two variants of the classical bin packing problem in which items may befragmented. This can potentially reduce the total number of bins needed for packing the instance. However, since fragmentation incurs overhead, we attempt to avoid it as much as possible. Inbin packing with size increasing fragmentation (BP-SIF), fragmenting an item increases the input size (due to a header/footer of fixed size that is added to each fragment). Inbin packing with size preserving fragmentation (BP-SPF), there is a bound on the total number of fragmented items. These two variants of bin packing capture many practical scenarios, including message transmission in community TV networks, VLSI circuit design and preemptive scheduling on parallel machines with setup times/setup costs.

While both BP-SPF and BP-SIF do not belong to the class of problems that admit apolynomial time approximation scheme (PTAS), we show in this paper that both problems admit adual PTAS and anasymptotic PTAS. We also develop for each of the problems a dual asymptoticfully polynomial time approximation scheme (AFPTAS). The AFPTASs are based on a non-trivial application of a fast combinatorial FPTAS for packing linear programs with negative entries, proposed recently by Garg and Khandekar [5].

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

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. Coffman Jr., E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, pp. 46–93. PWS Publishing, Boston (1997)

    Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

  3. Epstein, L., Sgall, J.: Approximation schemes for scheduling on uniformly related and identical parallel machines. In: Nešetřil, J. (ed.) ESA 1999. LNCS, vol. 1643, pp. 151–162. Springer, Heidelberg (1999)

    Google Scholar 

  4. Garey, M.R., Johnson, D.S.: Computers and Intractability: A guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco (1979)

    MATH  Google Scholar 

  5. Garg, N., Khandekar, R.: Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 371–382. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  6. Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica I, 169–197 (1981)

    Google Scholar 

  7. Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: Practical and theoretical results. Journal of the ACM 34(1), 144–162 (1987)

    Article  Google Scholar 

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

    Google Scholar 

  9. Khandekar, R.: Lagrangian relaxation based algorithms for convex programming problems. PhD thesis, Indian Institute of Technology Delhi (2004),http://www.cse.iitd.ernet.in/~rohitk

  10. Mandal, C.A., Chakrabarti, P.P., Ghose, S.: Complexity of fragmentable object bin packing and an application. Computers and Mathematics with Applications 35(11), 91–97 (1998)

    Article MathSciNet MATH  Google Scholar 

  11. McNaughton, R.: Scheduling with deadlines and loss functions. Manage. Sci. 6, 1–12 (1959)

    Article MathSciNet MATH  Google Scholar 

  12. Menakerman, N., Rom, R.: Bin Packing with Item Fragmentation. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol. 2125, p. 313. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  13. Motwani, R.: Lecture notes on approximation algorithms. Technical report, Dept. of Computer Science, Stanford Univ., CA (1992)

    Google Scholar 

  14. Multimedia Cable Network System Ltd., Data-Over-Cable Service Interface Specification (2000),http://www.cablelabs.com

  15. Naaman, N., Rom, R.: Packet Scheduling with Fragmentation. In: Proc. of INFOCOM 2002, pp. 824–831 (2002)

    Google Scholar 

  16. Shachnai, H., Tamir, T., Woeginger, G.J.: Minimizing Makespan and Preemption Costs on a System of Uniform Machines. Algorithmica 42, 309–334 (2005)

    Article MathSciNet MATH  Google Scholar 

  17. Shachnai, H., Tamir, T., Yehezkely, O.: Approximation Schemes for Packing with Item Fragmentation, Full version,http://www.cs.technion.ac.il/~hadas/PUB/frag.pdf

  18. Vazirani, V.V.: Bin Packing. In: Approximation Algorithms, pp. 74–78. Springer, Heidelberg (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, The Technion, Haifa, Israel

    Hadas Shachnai & Omer Yehezkely

  2. School of Computer Science, The Interdisciplinary Center, Herzliya, Israel

    Tami Tamir

Authors
  1. Hadas Shachnai
  2. Tami Tamir
  3. Omer Yehezkely

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of Leicester, University Road, LE1 7RH, Leicester, UK

    Thomas Erlebach

  2. Via Dipartimento di IInformatica ed Applicazioni, Universit{‘a degli Studi di Salerno, Via S. Allende 2, 84081, Baronissi, (SA), Italy

    Giuseppe Persinao

Rights and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Shachnai, H., Tamir, T., Yehezkely, O. (2006). Approximation Schemes for Packing with Item Fragmentation. In: Erlebach, T., Persinao, G. (eds) Approximation and Online Algorithms. WAOA 2005. Lecture Notes in Computer Science, vol 3879. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11671411_26

Download citation

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Publish with us

[8]ページ先頭
©2009-2026 Movatter.jp