Faster (1+ε)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back

Authors Fabrizio Grandoni, Tobias Mömke , Andreas Wiese



PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.49.pdf
  • Filesize: 0.75 MB
  • 15 pages

Document Identifiers

Author Details

Fabrizio Grandoni
  • IDSIA, USI-SUPSI, Lugano, Switzerland
Tobias Mömke
  • Department of Computer Science, Universität Augsburg, Germany
Andreas Wiese
  • Department of Industrial Engineering, Universidad de Chile, Santiago, Chile

Cite AsGet BibTex

Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese. Faster (1+ε)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.49

Abstract

Unsplittable flow on a path (UFP) is an important and well-studied problem. We are given a path with capacities on its edges, and a set of tasks where for each task we are given a demand, a subpath, and a weight. The goal is to select the set of tasks of maximum total weight whose total demands do not exceed the capacity on any edge. UFP admits an (1+ε)-approximation with a running time of n^{O_{ε}(poly(log n))}, i.e., a QPTAS {[}Bansal et al., STOC 2006; Batra et al., SODA 2015{]} and it is considered an important open problem to construct a PTAS. To this end, in a series of papers polynomial time approximation algorithms have been developed, which culminated in a (5/3+ε)-approximation {[}Grandoni et al., STOC 2018{]} and very recently an approximation ratio of (1+1/(e+1)+ε) < 1.269 {[}Grandoni et al., 2020{]}. In this paper, we address the search for a PTAS from a different angle: we present a faster (1+ε)-approximation with a running time of only n^{O_{ε}(log log n)}. We first give such a result in the relaxed setting of resource augmentation and then transform it to an algorithm without resource augmentation. For this, we present a framework which transforms algorithms for (a slight generalization of) UFP under resource augmentation in a black-box manner into algorithms for UFP without resource augmentation, with only negligible loss.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic programming
  • Theory of computation → Packing and covering problems
  • Theory of computation → Rounding techniques
Keywords
  • Approximation Algorithms
  • Unsplittable Flow
  • Dynamic Programming

Metrics

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

References

  1. Anna Adamaszek, Parinya Chalermsook, Alina Ene, and Andreas Wiese. Submodular unsplittable flow on trees. Math. Program., 172(1-2):565-589, 2018. URL: https://doi.org/10.1007/s10107-017-1218-4.
  2. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese. Constant integrality gap LP formulations of unsplittable flow on a path. In IPCO, pages 25-36, 2013. URL: https://doi.org/10.1007/978-3-642-36694-9_3.
  3. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese. A mazing 2+ε approximation for unsplittable flow on a path. ACM Trans. Algorithms, 14(4):55:1-55:23, 2018. URL: https://doi.org/10.1145/3242769.
  4. Y. Azar and O. Regev. Combinatorial algorithms for the unsplittable flow problem. Algorithmica, 44(1):49-66, 2006. URL: https://doi.org/10.1007/s00453-005-1172-z.
  5. N. Bansal, A. Chakrabarti, A. Epstein, and B. Schieber. A quasi-PTAS for unsplittable flow on line graphs. In STOC, pages 721-729. ACM, 2006. Google Scholar
  6. N. Bansal, Z. Friggstad, R. Khandekar, and R. Salavatipour. A logarithmic approximation for unsplittable flow on line graphs. In SODA, pages 702-709, 2009. Google Scholar
  7. 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. URL: https://doi.org/10.1137/1.9781611973730.5.
  8. Paul Bonsma, Jens Schulz, and Andreas Wiese. A constant-factor approximation algorithm for unsplittable flow on paths. SIAM Journal on Computing, 43:767-799, 2014. Google Scholar
  9. A. Chakrabarti, C. Chekuri, A. Gupta, and A. Kumar. Approximation algorithms for the unsplittable flow problem. Algorithmica, 47:53-78, 2007. Google Scholar
  10. C. Chekuri, A. Ene, and N. Korula. Unsplittable flow in paths and trees and column-restricted packing integer programs. In APPROX-RANDOM, pages 42-55, 2009. Google Scholar
  11. C. Chekuri, M. Mydlarz, and F. Shepherd. Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms, 3, 2007. Google Scholar
  12. M. Chrobak, G. Woeginger, K. Makino, and H. Xu. Caching is hard, even in the fault model. In ESA, pages 195-206, 2010. Google Scholar
  13. Julia Chuzhoy and Alina Ene. On approximating maximum independent set of rectangles. In IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), pages 820-829. IEEE, 2016. Google Scholar
  14. Fabrizio Grandoni, Salvatore Ingala, and Sumedha Uniyal. Improved approximation algorithms for unsplittable flow on a path with time windows. In WAOA, pages 13-24, 2015. Google Scholar
  15. Fabrizio Grandoni, Tobias Mömke, and Andreas Wiese. Unsplittable flow on a path: The game!, 2020. unpublished. Google Scholar
  16. 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
  17. 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 Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 607-619, 2018. URL: https://doi.org/10.1145/3188745.3188894.
  18. Shi Li. Towards PTAS for precedence constrained scheduling via combinatorial algorithms. In SODA, pages 2991-3010. SIAM, 2021. Google Scholar
  19. Andreas Wiese. A (1+epsilon)-approximation for unsplittable flow on a path in fixed-parameter running time. In ICALP 2017, volume 80 of LIPIcs, pages 67:1-67:13, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.67.
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