Document Open Access Logo

FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees

Authors Tomás Martínez-Muñoz, Andreas Wiese

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.67.pdf
  • Filesize: 0.76 MB
  • 15 pages

Document Identifiers

Author Details

Tomás Martínez-Muñoz
  • Mathematical Engineering Department, University of Chile, Santiago, Chile
Andreas Wiese
  • Department of Industrial Engineering, University of Chile, Santiago, Chile

Funding

  • Martínez-Muñoz, Tomás: Partially supported by CMM ANID PIA AFB170001.
  • Wiese, Andreas: Partially supported by FONDECYT Regular grant 1200173.

Cite As Get BibTex

Tomás Martínez-Muñoz and Andreas Wiese. FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 67:1-67:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.67

Abstract

We study the unsplittable flow on trees (UFT) problem in which we are given a tree with capacities on its edges and a set of tasks, where each task is described by a path and a demand. Our goal is to select a subset of the given tasks of maximum size such that the demands of the selected tasks respect the edge capacities. The problem models throughput maximization in tree networks. The best known approximation ratio for (unweighted) UFT is O(log n). We study the problem under the angle of FPT and FPT-approximation algorithms. We prove that  
- UFT is FPT if the parameters are the cardinality k of the desired solution and the number of different task demands in the input, 
- UFT is FPT under (1+δ)-resource augmentation of the edge capacities for parameters k and 1/δ, and 
- UFT admits an FPT-5-approximation algorithm for parameter k.  One key to our results is to compute structured hitting sets of the input edges which partition the given tree into O(k) clean components. This allows us to guess important properties of the optimal solution. Also, in some settings we can compute core sets of subsets of tasks out of which at least one task i is contained in the optimal solution. These sets have bounded size, and hence we can guess this task i easily.
A consequence of our results is that the integral multicommodity flow problem on trees is FPT if the parameter is the desired amount of sent flow. Also, even under (1+δ)-resource augmentation UFT is APX-hard, and hence our FPT-approximation algorithm for this setting breaks this boundary.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • FPT algorithms
  • FPT-approximation algorithms
  • packing problems
  • unsplittable flow
  • trees

Metrics

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

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. Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, and Michal Wlodarczyk. Constant factor FPT approximation for capacitated k-median. CoRR, abs/1809.05791, 2018. URL: http://arxiv.org/abs/1809.05791.
  3. Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual algorithms. SIAM Journal on Computing, 49(4):FOCS17-97, 2019. Google Scholar
  4. E. M. Arkin and E. B. Silverberg. Scheduling jobs with fixed start and end times. Discrete Applied Mathematics, 18:1-8, 1987. Google Scholar
  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. Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, and Dror Rawitz. Resource allocation in bounded degree trees. Algorithmica, 54(1):89-106, 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. Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 737-756. SIAM, 2014. Google Scholar
  9. Moses Charikar, Chandra Chekuri, Ashish Goel, and Sudipto Guha. Rounding via trees: deterministic approximation algorithms for group steiner trees and k-median. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC 1998), pages 114-123, 1998. 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. Bo Chen, Refael Hassin, and Michal Tzur. Allocation of bandwidth and storage. IIE Transactions, 34(5):501-507, 2002. Google Scholar
  13. Rajesh Chitnis, MohammadTaghi Hajiaghayi, and Guy Kortsarz. Fixed-parameter and approximation algorithms: A new look. In International Symposium on Parameterized and Exact Computation, pages 110-122. Springer, 2013. Google Scholar
  14. 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
  15. Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT Approximations for k-Median and k-Means. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1-42:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.42.
  16. Vincent Cohen-Addad and Jason Li. On the Fixed-Parameter Tractability of Capacitated Clustering. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 41:1-41:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.41.
  17. Andreas Emil Feldmann, CS Karthik, Euiwoong Lee, and Pasin Manurangsi. A survey on approximation in parameterized complexity: Hardness and algorithms. Algorithms, 13(6):146, 2020. Google Scholar
  18. Zachary Friggstad and Zhihan Gao. On Linear Programming Relaxations for Unsplittable Flow in Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), volume 40 of Leibniz International Proceedings in Informatics (LIPIcs), pages 265-283, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.265.
  19. N. Garg, V. Vazirani, and M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18:3-20, 1997. URL: https://doi.org/10.1007/BF02523685.
  20. 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.
  21. Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of algorithms, 31(1):228-248, 1999. Google Scholar
  22. Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 585-594, 2003. Google Scholar
  23. Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. In International Colloquium on Automata, Languages, and Programming, pages 77-88. Springer, 2011. Google Scholar
  24. Dániel Marx. Parameterized complexity and approximation algorithms. The Computer Journal, 51(1):60-78, 2008. Google Scholar
  25. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact