Document Open Access Logo

Sublinear-Round Parallel Matroid Intersection

Author Joakim Blikstad

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.25.pdf
  • Filesize: 0.78 MB
  • 17 pages

Document Identifiers

Author Details

Joakim Blikstad
  • KTH Royal Institute of Technology, 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. The author is also supported by the Swedish Research Council (Reg. No. 2019-05622).

Acknowledgements

I thank Danupon Nanongkai and Sagnik Mukhopadhyay for insightful discussions and their valuable comments throughout the development of this work. Part of this work was done while the author visited BARC and the University of Copenhagen.

Cite AsGet BibTex

Joakim Blikstad. Sublinear-Round Parallel Matroid Intersection. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.25

Abstract

Despite a lot of recent progress in obtaining faster sequential matroid intersection algorithms, the fastest parallel poly(n)-query algorithm was still the straightforward O(n)-round parallel implementation of Edmonds' augmenting paths algorithm from the 1960s. Very recently, Chakrabarty-Chen-Khanna [FOCS'21] showed the lower bound that any, possibly randomized, parallel matroid intersection algorithm making poly(n) rank-queries requires Ω̃(n^{1/3}) rounds of adaptivity. They ask, as an open question, if the lower bound can be improved to Ω̃(n), or if there can be sublinear-round, poly(n)-query algorithms for matroid intersection. We resolve this open problem by presenting the first sublinear-round parallel matroid intersection algorithms. Perhaps surprisingly, we do not only break the Õ(n)-barrier in the rank-oracle model, but also in the weaker independence-oracle model. Our rank-query algorithm guarantees O(n^{3/4}) rounds of adaptivity, while the independence-query algorithm uses O(n^{7/8}) rounds of adaptivity, both making a total of poly(n) queries.

Subject Classification

ACM Subject Classification
  • Theory of computation → Discrete optimization
  • Theory of computation → Parallel computing models
  • Theory of computation → Approximation algorithms analysis
  • Mathematics of computing → Matroids and greedoids
Keywords
  • Matroid Intersection
  • Combinatorial Optimization
  • Parallel 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. Breaking o(nr) for matroid intersection. In ICALP, volume 198 of LIPIcs, pages 31:1-31:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.31.
  3. Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, and Danupon Nanongkai. Breaking the quadratic barrier for matroid intersection. In STOC, pages 421-432. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451092.
  4. Deeparnab Chakrabarty, Yu Chen, and Sanjeev Khanna. A polynomial lower bound on the number of rounds for parallel submodular function minimization and matroid intersection. In FOCS, pages 37-48. IEEE Computer Society, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00013.
  5. 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. URL: https://doi.org/10.1109/FOCS.2019.00072.
  6. William H. Cunningham. Improved bounds for matroid partition and intersection algorithms. SIAM J. Comput., 15(4):948-957, 1986. URL: https://doi.org/10.1137/0215066.
  7. Efim A Dinic. Algorithm for solution of a problem of maximum flow in networks with power estimation. In Soviet Math. Doklady, volume 11, pages 1277-1280, 1970. Google Scholar
  8. Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial structures and their applications, pages 69-87. Gordon and Breach, 1970. Google Scholar
  9. Jack Edmonds. Matroid intersection. In Annals of discrete Mathematics, volume 4, pages 39-49. Elsevier, 1979. Google Scholar
  10. Jack Edmonds, GB Dantzig, AF Veinott, and M Jünger. Matroid partition. 50 Years of Integer Programming 1958-2008, page 199, 1968. Google Scholar
  11. Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-nc. SIAM J. Comput., 50(3), 2021. URL: https://doi.org/10.1137/16M1097870.
  12. Sumanta Ghosh, Rohit Gurjar, and Roshan Raj. A deterministic parallel reduction from weighted matroid intersection search to decision. In SODA, pages 1013-1035. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.44.
  13. Rohit Gurjar and Thomas Thierauf. Linear matroid intersection is in quasi-nc. Comput. Complex., 29(2):9, 2020. URL: https://doi.org/10.1007/s00037-020-00200-z.
  14. John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4):225-231, 1973. URL: https://doi.org/10.1137/0202019.
  15. Richard M. Karp, Eli Upfal, and Avi Wigderson. The complexity of parallel computation on matroids. In FOCS, pages 541-550. IEEE Computer Society, 1985. URL: https://doi.org/10.1109/SFCS.1985.57.
  16. Richard M. Karp, Eli Upfal, and Avi Wigderson. Constructing a perfect matching is in random NC. Comb., 6(1):35-48, 1986. URL: https://doi.org/10.1007/BF02579407.
  17. Richard M. Karp, Eli Upfal, and Avi Wigderson. The complexity of parallel search. J. Comput. Syst. Sci., 36(2):225-253, 1988. URL: https://doi.org/10.1016/0022-0000(88)90027-X.
  18. Eugene L. Lawler. Matroid intersection algorithms. Math. Program., 9(1):31-56, 1975. URL: https://doi.org/10.1007/BF01681329.
  19. 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. URL: https://doi.org/10.1109/FOCS.2015.68.
  20. László Lovász. On determinants, matchings, and random algorithms. In FCT, pages 565-574. Akademie-Verlag, Berlin, 1979. Google Scholar
  21. 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