Document Open Access Logo

Breaking O(nr) for Matroid Intersection

Author Joakim Blikstad

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.31.pdf
  • Filesize: 0.85 MB
  • 17 pages

Document Identifiers

Author Details

Joakim Blikstad
  • KTH Royal Institute of Technology, Stockholm, Sweden

Funding

This project has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme under grant agreement No 71567.

Acknowledgements

I thank Danupon Nanongkai and Sagnik Mukhopadhyay for insightful discussions and their valuable comments throughout the development of this work.

Cite AsGet BibTex

Joakim Blikstad. Breaking O(nr) for Matroid Intersection. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.31

Abstract

We present algorithms that break the Õ(nr)-independence-query bound for the Matroid Intersection problem for the full range of r; where n is the size of the ground set and r ≤ n is the size of the largest common independent set. The Õ(nr) bound was due to the efficient implementations [CLSSW FOCS'19; Nguyên 2019] of the classic algorithm of Cunningham [SICOMP'86]. It was recently broken for large r (r = ω(√n)), first by the Õ(n^{1.5}/ε^{1.5})-query (1-ε)-approximation algorithm of CLSSW [FOCS'19], and subsequently by the Õ(n^{6/5}r^{3/5})-query exact algorithm of BvdBMN [STOC'21]. No algorithm - even an approximation one - was known to break the Õ(nr) bound for the full range of r. We present an Õ(n√r/ε)-query (1-ε)-approximation algorithm and an Õ(nr^{3/4})-query exact algorithm. Our algorithms improve the Õ(nr) bound and also the bounds by CLSSW and BvdBMN for the full range of r.

Subject Classification

ACM Subject Classification
  • Theory of computation → Discrete optimization
  • Theory of computation → Approximation algorithms analysis
  • Mathematics of computing → Matroids and greedoids
Keywords
  • Matroid Intersection
  • Combinatorial Optimization
  • Approximation Algorithms

Metrics

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

References

  1. Martin Aigner and Thomas A. Dowling. Matching theory for combinatorial geometries. Transactions of the American Mathematical Society, 158(1):231-245, 1971. Google Scholar
  2. Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, and Danupon Nanongkai. Breaking the quadratic barrier for matroid intersection. In STOC. ACM, 2021. Google Scholar
  3. Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, and Sam Chiu-wai Wong. Faster matroid intersection. In FOCS, pages 1146-1168. IEEE Computer Society, 2019. Google Scholar
  4. Chandra Chekuri and Kent Quanrud. A fast approximation for maximum weight matroid intersection. In SODA, pages 445-457. SIAM, 2016. Google Scholar
  5. William H. Cunningham. Improved bounds for matroid partition and intersection algorithms. SIAM J. Comput., 15(4):948-957, 1986. Google Scholar
  6. Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial structures and their applications, pages 69-87. Gordon and Breach, 1970. Google Scholar
  7. Jack Edmonds. Matroid intersection. In Annals of discrete Mathematics, volume 4, pages 39-49. Elsevier, 1979. Google Scholar
  8. Jack Edmonds, GB Dantzig, AF Veinott, and M Jünger. Matroid partition. 50 Years of Integer Programming 1958-2008, page 199, 1968. Google Scholar
  9. Eugene L. Lawler. Matroid intersection algorithms. Math. Program., 9(1):31-56, 1975. Google Scholar
  10. Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In FOCS, pages 1049-1065. IEEE Computer Society, 2015. Google Scholar
  11. Huy L. Nguyen. A note on cunningham’s algorithm for matroid intersection. CoRR, abs/1904.04129, 2019. URL: http://arxiv.org/abs/1904.04129.
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 Imprint Privacy Contact