Document Open Access Logo

Budgeted Matroid Maximization: a Parameterized Viewpoint

Authors Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai

PDF

File

Thumbnail PDF
PDF
LIPIcs.IPEC.2023.13.pdf
  • Filesize: 0.81 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • budgeted matching
  • budgeted matroid intersection
  • knapsack problems
  • FPT-approximation scheme

Metrics

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

Abstract

We study budgeted variants of well known maximization problems with multiple matroid constraints. Given an 𝓁-matchoid ℳ on a ground set E, a profit function p:E → ℝ_{≥ 0}, a cost function c:E → ℝ_{≥ 0}, and a budget B ∈ ℝ_{≥ 0}, the goal is to find in the 𝓁-matchoid a feasible set S of maximum profit p(S) subject to the budget constraint, i.e., c(S) ≤ B. The budgeted 𝓁-matchoid (BM) problem includes as special cases budgeted 𝓁-dimensional matching and budgeted 𝓁-matroid intersection. A strong motivation for studying BM from parameterized viewpoint comes from the APX-hardness of unbudgeted 𝓁-dimensional matching (i.e., B = ∞) already for 𝓁 = 3. Nevertheless, while there are known FPT algorithms for the unbudgeted variants of the above problems, the budgeted variants are studied here for the first time through the lens of parameterized complexity.
We show that BM parametrized by solution size is W[1]-hard, already with a degenerate single matroid constraint. Thus, an exact parameterized algorithm is unlikely to exist, motivating the study of FPT-approximation schemes (FPAS). Our main result is an FPAS for BM (implying an FPAS for 𝓁-dimensional matching and budgeted 𝓁-matroid intersection), relying on the notion of representative set - a small cardinality subset of elements which preserves the optimum up to a small factor. We also give a lower bound on the minimum possible size of a representative set which can be computed in polynomial time.

Cite As Get BibTex

Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. Budgeted Matroid Maximization: a Parameterized Viewpoint. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.IPEC.2023.13

Author Details

Ilan Doron-Arad
  • Computer Science Department, Technion, Haifa, Israel
Ariel Kulik
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Hadas Shachnai
  • Computer Science Department, Technion, Haifa, Israel

Funding

  • Kulik, Ariel: Research supported by the European Reseach Concil (ERC) consolidator grant no. 725978 SYSTEMATICGRAPH.

References

  1. André Berger, Vincenzo Bonifaci, Fabrizio Grandoni, and Guido Schäfer. Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Mathematical Programming, 128(1):355-372, 2011. Google Scholar
  2. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. Journal of Computer and System Sciences, 87:119-139, 2017. Google Scholar
  3. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Multi-budgeted matchings and matroid intersection via dependent rounding. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1080-1097. SIAM, 2011. Google Scholar
  4. Jianer Chen, Qilong Feng, Yang Liu, Songjian Lu, and Jianxin Wang. Improved deterministic algorithms for weighted matching and packing problems. Theoretical computer science, 412(23):2503-2512, 2011. Google Scholar
  5. Holger Dell and Dániel Marx. Kernelization of packing problems. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 68-81. SIAM, 2012. Google Scholar
  6. Holger Dell and Dániel Marx. Kernelization of packing problems. arXiv preprint arXiv:1812.03155, 2018. Google Scholar
  7. Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. Budgeted matroid maximization: a parameterized viewpoint. arXiv preprint arXiv:2307.04173, 2023. Google Scholar
  8. Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An EPTAS for budgeted matching and budgeted matroid intersection via representative sets. In 50th International Colloquium on Automata, Languages, and Programming (ICALP), 2023. Google Scholar
  9. Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An EPTAS for budgeted matroid independent set. In Symposium on Simplicity in Algorithms (SOSA), pages 69-83, 2023. Google Scholar
  10. Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. An FPTAS for budgeted laminar matroid independent set. Operations Research Letters, 51(6):632-637, 2023. URL: https://doi.org/10.1016/j.orl.2023.10.005.
  11. Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. Tight lower bounds for weighted matroid problems. arXiv preprint arXiv:2307.07773, 2023. Google Scholar
  12. Rod G Downey and Michael R Fellows. Fixed-parameter tractability and completeness ii: On completeness for W[1]. Theoretical Computer Science, 141(1-2):109-131, 1995. Google Scholar
  13. Moran Feldman, Joseph Naor, Roy Schwartz, and Justin Ward. Improved approximations for k-exchange systems. In Algorithms-ESA 2011: 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings 19, pages 784-798. Springer, 2011. Google Scholar
  14. Andreas Emil Feldmann, Euiwoong Lee, and Pasin Manurangsi. A survey on approximation in parameterized complexity: Hardness and algorithms. Algorithms, 13(6):146, 2020. Google Scholar
  15. Fedor V Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM (JACM), 63(4):1-60, 2016. Google Scholar
  16. Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: theory of parameterized preprocessing. Cambridge University Press, 2019. Google Scholar
  17. Alan M Frieze, Michael RB Clarke, et al. Approximation algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses. European Journal of Operational Research, 15(1):100-109, 1984. Google Scholar
  18. Michael R Garey and David S Johnson. Computers and intractability, volume 174. freeman San Francisco, 1979. Google Scholar
  19. Prachi Goyal, Neeldhara Misra, Fahad Panolan, and Meirav Zehavi. Deterministic algorithms for matching and packing problems based on representative sets. SIAM Journal on Discrete Mathematics, 29(4):1815-1836, 2015. Google Scholar
  20. Fabrizio Grandoni and Rico Zenklusen. Approximation schemes for multi-budgeted independence systems. In European Symposium on Algorithms, pages 536-548. Springer, 2010. Google Scholar
  21. Chien-Chung Huang and Justin Ward. FPT-algorithms for the 𝓁-matchoid problem with a coverage objective. arXiv preprint arXiv:2011.06268, 2020. Google Scholar
  22. Chien-Chung Huang and Justin Ward. FPT-algorithms for the 𝓁-matchoid problem with a coverage objective. SIAM Journal on Discrete Mathematics, 2023. Google Scholar
  23. Th Jenkyns. The efficacy of the "greedy" algorithm. In Proc. 7th Southeastern Conf. on Combinatorics, Graph Theory and Computing, pages 341-350, 1976. Google Scholar
  24. Per M Jensen and Bernhard Korte. Complexity of matroid property algorithms. SIAM Journal on Computing, 11(1):184-190, 1982. Google Scholar
  25. Stasys Jukna. Extremal combinatorics: with applications in computer science, volume 571. Springer, 2011. Google Scholar
  26. Viggo Kann. Maximum bounded 3-dimensional matching is max snp-complete. Information Processing Letters, 37(1):27-35, 1991. Google Scholar
  27. Ioannis Koutis and Ryan Williams. Limits and applications of group algebras for parameterized problems. In Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I 36, pages 653-664. Springer, 2009. Google Scholar
  28. Ariel Kulik and Hadas Shachnai. There is no EPTAS for two-dimensional knapsack. Information Processing Letters, 110(16):707-710, 2010. Google Scholar
  29. Ariel Kulik, Hadas Shachnai, and Gal Tamir. On lagrangian relaxation for constrained maximization and reoptimization problems. Discrete Applied Mathematics, 296:164-178, 2021. Google Scholar
  30. Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh. Deterministic truncation of linear matroids. ACM Transactions on Algorithms (TALG), 14(2):1-20, 2018. Google Scholar
  31. Daniel Lokshtanov, Fahad Panolan, MS Ramanujan, and Saket Saurabh. Lossy kernelization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 224-237, 2017. Google Scholar
  32. László Lovász. Matroid matching and some applications. Journal of Combinatorial Theory, Series B, 28(2):208-236, 1980. Google Scholar
  33. Silvano Martello and Paolo Toth. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., 1990. Google Scholar
  34. Dániel Marx. Parameterized complexity and approximation algorithms. The Computer Journal, 51(1):60-78, 2008. Google Scholar
  35. Dániel Marx. A parameterized view on matroid optimization problems. Theoretical Computer Science, 410(44):4471-4479, 2009. Google Scholar
  36. Ram Ravi and Michel X Goemans. The constrained minimum spanning tree problem. In Scandinavian Workshop on Algorithm Theory, pages 66-75. Springer, 1996. Google Scholar
  37. Alexander Schrijver et al. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact
OSZAR »