Document Open Access Logo

Approximation Algorithms for Round-UFP and Round-SAP

Authors Debajyoti Kar, Arindam Khan , Andreas Wiese

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.71.pdf
  • Filesize: 0.88 MB
  • 19 pages

Document Identifiers

Author Details

Debajyoti Kar
  • Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India
Arindam Khan
  • Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India
Andreas Wiese
  • Department of Mathematics, Technische Unviersität Müchen, Germany

Funding

  • Khan, Arindam: Arindam Khan was supported in part by Pratiksha Trust Young Investigator Award, Google CSExplore Award, and Google India Research Award.

Acknowledgements

We thank Waldo G{á}lvez, Afrouz Jabal Ameli, Siba Smarak Panigrahi, and Arka Ray for helpful initial discussions.

Cite As Get BibTex

Debajyoti Kar, Arindam Khan, and Andreas Wiese. Approximation Algorithms for Round-UFP and Round-SAP. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 71:1-71:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.71

Abstract

We study Round-UFP and Round-SAP, two generalizations of the classical Bin Packing problem that correspond to the unsplittable flow problem on a path (UFP) and the storage allocation problem (SAP), respectively. We are given a path with capacities on its edges and a set of jobs where for each job we are given a demand and a subpath. In Round-UFP, the goal is to find a packing of all jobs into a minimum number of copies (rounds) of the given path such that for each copy, the total demand of jobs on any edge does not exceed the capacity of the respective edge. In Round-SAP, the jobs are considered to be rectangles and the goal is to find a non-overlapping packing of these rectangles into a minimum number of rounds such that all rectangles lie completely below the capacity profile of the edges.
We show that in contrast to Bin Packing, both problems do not admit an asymptotic polynomial-time approximation scheme (APTAS), even when all edge capacities are equal. However, for this setting, we obtain asymptotic (2+ε)-approximations for both problems. For the general case, we obtain an O(log log n)-approximation algorithm and an O(log log 1/δ)-approximation under (1+δ)-resource augmentation for both problems. For the intermediate setting of the no bottleneck assumption (i.e., the maximum job demand is at most the minimum edge capacity), we obtain an absolute 12- and an asymptotic (16+ε)-approximation algorithm for Round-UFP and Round-SAP, respectively.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Approximation Algorithms
  • Scheduling
  • Rectangle Packing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese. Approximation schemes for independent set and sparse subsets of polygons. Journal of the ACM, 66(4):29:1-29:40, 2019. Google Scholar
  2. Udo Adamy and Thomas Erlebach. Online coloring of intervals with bandwidth. In WAOA, pages 1-12. Springer, 2003. Google Scholar
  3. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese. A mazing 2+ε approximation for unsplittable flow on a path. In SODA, pages 26-41, 2014. Google Scholar
  4. Matthew Andrews and Lisa Zhang. Bounds on fiber minimization in optical networks with fixed fiber capacity. In 24th Annual Joint Conference of the IEEE Computer and Communications Societies, volume 1, pages 409-419, 2005. Google Scholar
  5. Yossi Azar, Amos Fiat, Meital Levy, and NS Narayanaswamy. An improved algorithm for online coloring of intervals with bandwidth. Theoretical Computer Science, 363(1):18-27, 2006. Google Scholar
  6. Nikhil Bansal, José R Correa, Claire Kenyon, and Maxim Sviridenko. Bin packing in multiple dimensions: inapproximability results and approximation schemes. Mathematics of operations research, 31(1):31-49, 2006. Google Scholar
  7. Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, and Mohammad R Salavatipour. A logarithmic approximation for unsplittable flow on line graphs. ACM Transactions on Algorithms (TALG), 10(1):1-15, 2014. Google Scholar
  8. Nikhil Bansal and Arindam Khan. Improved approximation algorithm for two-dimensional bin packing. In SODA, pages 13-25, 2014. Google Scholar
  9. Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, and Andreas Wiese. New approximation schemes for unsplittable flow on a path. In SODA, pages 47-58, 2015. Google Scholar
  10. Paul S. Bonsma, Jens Schulz, and Andreas Wiese. A constant factor approximation algorithm for unsplittable flow on paths. In FOCS, pages 47-56, 2011. Google Scholar
  11. Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, and Mikkel Thorup. OPT versus LOAD in dynamic storage allocation. In STOC, pages 556-564, 2003. Google Scholar
  12. Parinya Chalermsook and Bartosz Walczak. Coloring and maximum weight independent set of rectangles. In SODA, pages 860-868, 2021. Google Scholar
  13. Chandra Chekuri and Sanjeev Khanna. A polynomial time approximation scheme for the multiple knapsack problem. SIAM Journal on Computing, 35(3):713-728, 2005. Google Scholar
  14. Chandra Chekuri, Marcelo Mydlarz, and F. Bruce Shepherd. Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms (TALG), 3(3):27, 2007. Google Scholar
  15. Miroslav Chlebík and Janka Chlebíková. Complexity of approximating bounded variants of optimization problems. Theoretical Computer Science, 354(3):320-338, 2006. Google Scholar
  16. Miroslav Chlebík and Janka Chlebíková. Hardness of approximation for orthogonal rectangle packing and covering problems. Journal of Discrete Algorithms, 7(3):291-305, 2009. Google Scholar
  17. Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 24:63-79, 2017. Google Scholar
  18. Julia Chuzhoy and Shi Li. A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. Journal of the ACM, 63(5):1-51, 2016. Google Scholar
  19. W Fernandez De La Vega and George S. Lueker. Bin packing can be solved within 1 + ε in linear time. Combinatorica, 1(4):349-355, 1981. Google Scholar
  20. Max A Deppert, Klaus Jansen, Arindam Khan, Malin Rau, and Malte Tutas. Peak demand minimization via sliced strip packing. In APPROX/RANDOM, volume 207, pages 21:1-21:24, 2021. Google Scholar
  21. Khaled M. Elbassioni, Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula, and Arindam Pal. Approximation algorithms for the unsplittable flow problem on paths and trees. In FSTTCS, pages 267-275, 2012. Google Scholar
  22. Leah Epstein, Thomas Erlebach, and Asaf Levin. Online capacitated interval coloring. SIAM Journal on Discrete Mathematics, 23(2):822-841, 2009. Google Scholar
  23. Thomas Erlebach and Klaus Jansen. Off-line and on-line call-scheduling in stars and trees. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 199-213. Springer, 1997. Google Scholar
  24. Thomas Erlebach and Klaus Jansen. The complexity of path coloring and call scheduling. Theoretical Computer Science, 255(1-2):33-50, 2001. Google Scholar
  25. Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan, and Malin Rau. A tight (3/2+ε) approximation for skewed strip packing. In APPROX/RANDOM, pages 44:1-44:18, 2020. Google Scholar
  26. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via l-packings. In FOCS, pages 260-271, 2017. Google Scholar
  27. Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, and Arindam Khan. Improved pseudo-polynomial-time approximation for strip packing. In FSTTCS, pages 9:1-9:14, 2016. Google Scholar
  28. Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero, and Andreas Wiese. Improved approximation algorithms for 2-dimensional knapsack: Packing into multiple l-shapes, spirals, and more. In SoCG, volume 189, pages 39:1-39:17, 2021. Google Scholar
  29. Waldo Gálvez, Arindam Khan, Mathieu Mari, Tobias Mömke, Madhusudhan Reddy, and Andreas Wiese. A (2+ε)-approximation algorithm for maximum independent set of rectangles. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.00623.
  30. Jordan Gergov. Algorithms for compile-time memory optimization. In SODA, pages 907-908, 1999. Google Scholar
  31. Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese. A PTAS for unsplittable flow on a path. In STOC, pages 289-302, 2022. Google Scholar
  32. Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese. Unsplittable flow on a path: The game! In SODA, pages 906-926, 2022. Google Scholar
  33. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. To augment or not to augment: Solving unsplittable flow on a path by creating slack. In SODA, pages 2411-2422, 2017. Google Scholar
  34. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes. In STOC, pages 607-619, 2018. Google Scholar
  35. Hamidreza Jahanjou, Erez Kantor, and Rajmohan Rajaraman. Improved algorithms for scheduling unsplittable flows on paths. In ISAAC, pages 49:1-49:12, 2017. Google Scholar
  36. Klaus Jansen, Arindam Khan, Marvin Lira, and K. V. N. Sreenivas. A PTAS for packing hypercubes into a knapsack. In ICALP, volume 229, pages 78:1-78:20, 2022. Google Scholar
  37. Klaus Jansen and Guochuan Zhang. On rectangle packing: maximizing benefits. In SODA, pages 204-213, 2004. Google Scholar
  38. Arindam Khan. Approximation algorithms for multidimensional bin packing. PhD thesis, Georgia Institute of Technology, 2015. Google Scholar
  39. Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, and Andreas Wiese. Tight approximation algorithms for two-dimensional guillotine strip packing. In ICALP, volume 229, pages 80:1-80:20, 2022. Google Scholar
  40. Arindam Khan, Arnab Maiti, Amatya Sharma, and Andreas Wiese. On guillotine separable packings for the two-dimensional geometric knapsack problem. In SoCG, volume 189, pages 48:1-48:17, 2021. Google Scholar
  41. Arindam Khan and Madhusudhan Reddy Pittu. On guillotine separability of squares and rectangles. In APPROX/RANDOM, pages 47:1-47:22, 2020. Google Scholar
  42. Arindam Khan and Eklavya Sharma. Tight approximation algorithms for geometric bin packing with skewed items. In APPROX/RANDOM, volume 207, pages 22:1-22:23, 2021. Google Scholar
  43. Arindam Khan and Mohit Singh. On weighted bipartite edge coloring. In FSTTCS, pages 136-150, 2015. Google Scholar
  44. Joseph SB Mitchell. Approximating maximum independent set for rectangles in the plane. In FOCS, pages 339-350, 2022. Google Scholar
  45. Tobias Mömke and Andreas Wiese. A (2+ε)-approximation algorithm for the storage allocation problem. In ICALP, pages 973-984, 2015. Google Scholar
  46. Tobias Mömke and Andreas Wiese. Breaking the barrier of 2 for the storage allocation problem. In ICALP, pages 86:1-86:19, 2020. Google Scholar
  47. NS Narayanaswamy. Dynamic storage allocation and on-line colouring interval graphs. In COCOON, pages 329-338. Springer, 2004. Google Scholar
  48. Christos Nomikos, Aris Pagourtzis, and Stathis Zachos. Routing and path multicoloring. Inf. Process. Lett., 80(5):249-256, 2001. Google Scholar
  49. Arindam Pal. Approximation algorithms for covering and packing problems on paths. arXiv preprint, 2014. URL: http://arxiv.org/abs/1402.1107.
  50. Arka Ray. There is no aptas for 2-dimensional vector bin packing: Revisited. arXiv preprint, 2021. URL: http://arxiv.org/abs/2104.13362.
  51. Peter Winkler and Lisa Zhang. Wavelength assignment and generalized interval graph coloring. In SODA, pages 830-831, 2003. Google Scholar
  52. Gerhard J Woeginger. There is no asymptotic ptas for two-dimensional vector packing. Information Processing Letters, 64(6):293-297, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact