Document Open Access Logo

Subquadratic Weighted Matroid Intersection Under Rank Oracles

Author Ta-Wei Tu

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.63.pdf
  • Filesize: 0.76 MB
  • 14 pages

Document Identifiers

Author Details

Ta-Wei Tu
  • National Taiwan University, Taipei, Taiwan

Acknowledgements

I would like to thank Prof. Hsueh-I Lu for advising the project and helpful suggestions on the writing and notation. I also thank Min-Yen Tsai for proof-reading an initial draft of this paper and the anonymous reviewers of ISAAC 2022 for their useful comments.

Cite As Get BibTex

Ta-Wei Tu. Subquadratic Weighted Matroid Intersection Under Rank Oracles. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.63

Abstract

Given two matroids ℳ₁ = (V, ℐ₁) and ℳ₂ = (V, ℐ₂) over an n-element integer-weighted ground set V, the weighted matroid intersection problem aims to find a common independent set S^* ∈ ℐ₁ ∩ ℐ₂ maximizing the weight of S^*. In this paper, we present a simple deterministic algorithm for weighted matroid intersection using Õ(nr^{3/4} log{W}) rank queries, where r is the size of the largest intersection of ℳ₁ and ℳ₂ and W is the maximum weight. This improves upon the best previously known Õ(nr log{W}) algorithm given by Lee, Sidford, and Wong [FOCS'15], and is the first subquadratic algorithm for polynomially-bounded weights under the standard independence or rank oracle models. The main contribution of this paper is an efficient algorithm that computes shortest-path trees in weighted exchange graphs.

Subject Classification

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

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. URL: https://doi.org/10.2307/1995784.
  2. Joakim Blikstad. Breaking o(nr) for matroid intersection. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, 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 Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 421-432. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451092.
  4. Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, and Sam Chiu-wai Wong. Faster matroid intersection. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 1146-1168. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00072.
  5. Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. Subquadratic submodular function minimization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1220-1231. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055419.
  6. Chandra Chekuri and Kent Quanrud. A fast approximation for maximum weight matroid intersection. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 445-457. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch33.
  7. 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.
  8. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959. URL: https://doi.org/10.1007/BF01386390.
  9. Jack Edmonds. Matroids and the greedy algorithm. Math. Program., 1(1):127-136, 1971. URL: https://doi.org/10.1007/BF01584082.
  10. Jack Edmonds. Matroid intersection. Annals of Discrete Mathematics, 4:39-49, 1979. URL: https://doi.org/10.1016/S0167-5060(08)70817-3.
  11. Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Optimization - Eureka, You Shrink!, Papers Dedicated to Jack Edmonds, 5th International Workshop, volume 2570 of Lecture Notes in Computer Science, pages 11-26. Springer, 2001. URL: https://doi.org/10.1007/3-540-36478-1_2.
  12. Jack Edmonds. Matroid partition. In 50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art, pages 199-217. Springer, 2010. URL: https://doi.org/10.1007/978-3-540-68279-0_7.
  13. András Frank. A weighted matroid intersection algorithm. J. Algorithms, 2(4):328-336, 1981. URL: https://doi.org/10.1016/0196-6774(81)90032-8.
  14. Satoru Fujishige and Xiaodong Zhang. An efficient cost scaling algorithm for the independent assignment problem. Journal of the Operations Research Society of Japan, 38(1):124-136, 1995. URL: https://doi.org/10.15807/jorsj.38.124.
  15. Harold N. Gabow and Ying Xu. Efficient theoretic and practical algorithms for linear matroid intersection problems. J. Comput. Syst. Sci., 53(1):129-147, 1996. URL: https://doi.org/10.1006/jcss.1996.0054.
  16. Chien-Chung Huang, Naonori Kakimura, and Naoyuki Kamiyama. Exact and approximation algorithms for weighted matroid intersection. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 430-444. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch32.
  17. Eugene L. Lawler. Matroid intersection algorithms. Math. Program., 9(1):31-56, 1975. URL: https://doi.org/10.1007/BF01681329.
  18. Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pages 1049-1065. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/FOCS.2015.68.
  19. Huy L. Nguyen. A note on cunningham’s algorithm for matroid intersection. CoRR, abs/1904.04129, 2019. URL: http://arxiv.org/abs/1904.04129.
  20. James B. Orlin and Ravindra K. Ahuja. New scaling algorithms for the assignment and minimum mean cycle problems. Math. Program., 54:41-56, 1992. URL: https://doi.org/10.1007/BF01586040.
  21. Christopher Price. Combinatorial algorithms for submodular function minimization and related problems. Master’s thesis, University of Waterloo, 2015. URL: http://hdl.handle.net/10012/9356.
  22. Alexander Schrijver et al. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003. Google Scholar
  23. Maiko Shigeno and Satoru Iwata. A dual approximation approach to weighted matroid intersection. Oper. Res. Lett., 18(3):153-156, 1995. URL: https://doi.org/10.1016/0167-6377(95)00047-X.
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