Document Open Access Logo

Faster Matroid Partition Algorithms

Author Tatsuya Terao

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.104.pdf
  • Filesize: 0.83 MB
  • 20 pages

Document Identifiers

Author Details

Tatsuya Terao
  • Research Institute for Mathematical Sciences, Kyoto University, Japan

Funding

This work was partially supported by the joint project of Kyoto University and Toyota Motor Corporation, titled "Advanced Mathematical Science for Mobility Society".

Acknowledgements

The author thanks Yusuke Kobayashi for his generous support and helpful comments on the manuscript. The author also thanks the three anonymous reviewers for their valuable comments.

Cite As Get BibTex

Tatsuya Terao. Faster Matroid Partition Algorithms. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 104:1-104:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.104

Abstract

In the matroid partitioning problem, we are given k matroids ℳ₁ = (V, ℐ_1), … , ℳ_k = (V, ℐ_k) defined over a common ground set V of n elements, and we need to find a partitionable set S ⊆ V of largest possible cardinality, denoted by p. Here, a set S ⊆ V is called partitionable if there exists a partition (S_1, … , S_k) of S with S_i ∈ ℐ_i for i = 1, …, k. In 1986, Cunningham [Cunningham, 1986] presented a matroid partition algorithm that uses O(n p^{3/2} + k n) independence oracle queries, which was the previously known best algorithm. This query complexity is O(n^{5/2}) when k ≤ n.
Our main result is to present a matroid partition algorithm that uses Õ(k^{1/3} n p + k n) independence oracle queries, which is Õ(n^{7/3}) when k ≤ n. This improves upon previous Cunningham’s algorithm. To obtain this, we present a new approach edge recycling augmentation, which can be attained through new ideas: an efficient utilization of the binary search technique by Nguyễn [Nguyen, 2019] and Chakrabarty-Lee-Sidford-Singla-Wong [Chakrabarty et al., 2019] and a careful analysis of the number of independence oracle queries. Our analysis differs significantly from the one for matroid intersection algorithms, because of the parameter k. We also present a matroid partition algorithm that uses Õ((n + k) √p) rank oracle queries.

Subject Classification

ACM Subject Classification
  • Theory of computation → Discrete optimization
  • Theory of computation → Algorithm design techniques
  • Mathematics of computing → Matroids and greedoids
Keywords
  • Matroid Partition
  • Matroid Union
  • Combinatorial Optimization

Metrics

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

Related Versions

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 the 48th International Colloquium on Automata, Languages, and Programming (ICALP2022), pages 31:1-31:17, 2021. Google Scholar
  3. Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai Nanongkai, and Ta-Wei Tu. Fast algorithms via dynamic-oracle matroids. In the 55th ACM Symposium on Theory of Computing (STOC2023), to appear, 2023. Google Scholar
  4. Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, and Danupon Nanongkai. Breaking the quadratic barrier for matroid intersection. In the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC2021), pages 421-432, 2021. Google Scholar
  5. Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, and Sam Chiu-wai Wong. Faster matroid intersection. In the 60th Annual Symposium on Foundations of Computer Science (FOCS2019), pages 1146-1168. IEEE, 2019. Google Scholar
  6. Chandra Chekuri and Kent Quanrud. A fast approximation for maximum weight matroid intersection. In the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2016), pages 445-457. SIAM, 2016. Google Scholar
  7. William H Cunningham. Improved bounds for matroid partition and intersection algorithms. SIAM Journal on Computing, 15(4):948-957, 1986. Google Scholar
  8. Jack Edmonds. Matroid partition. Mathematics of the Decision Sciences, 11:335, 1968. Google Scholar
  9. Jack Edmonds. Submodular functions, matroids, and certain polyhedra. Combinatorial Structures and Their Applications, R. Guy, H. Hanani, N. Sauer, and J. Schonheim, eds. New York, pages 69-87, 1970. Google Scholar
  10. Jack Edmonds. Matroid intersection. In Annals of Discrete Mathematics, volume 4, pages 39-49. Elsevier, 1979. Google Scholar
  11. Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Optimization—Eureka, You Shrink! Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5-9, 2001 Revised Papers, pages 11-26. Springer, 2003. Google Scholar
  12. András Frank and Zoltán Miklós. Simple push-relabel algorithms for matroids and submodular flows. Japan Journal of Industrial and Applied Mathematics, 29:419-439, 2012. Google Scholar
  13. Harold Gabow and Herbert Westermann. Forests, frames, and games: algorithms for matroid sums and applications. In the Twentieth Annual ACM Symposium on Theory of Computing (STOC1988), pages 407-421, 1988. Google Scholar
  14. Curtis Greene and Thomas L Magnanti. Some abstract pivot algorithms. SIAM Journal on Applied Mathematics, 29(3):530-539, 1975. Google Scholar
  15. Nicholas JA Harvey. Matroid intersection, pointer chasing, and young’s seminormal representation of s_n. In the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2008), pages 542-549, 2008. Google Scholar
  16. Julian Haselmayr. Schnitt von matroiden theorie und algorithmen. Master’s thesis, University of Augsberg, 2008. Google Scholar
  17. John E Hopcroft and Richard M Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225-231, 1973. Google Scholar
  18. Chien-Chung Huang, Naonori Kakimura, and Naoyuki Kamiyama. Exact and approximation algorithms for weighted matroid intersection. In the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA2016), pages 430-444. SIAM, 2016. Google Scholar
  19. Yasushi Kawase, Kei Kimura, Kazuhisa Makino, and Hanna Sumita. Optimal matroid partitioning problems. Algorithmica, 83:1653-1676, 2021. Google Scholar
  20. Donald Ervin Knuth. Matroid partitioning. Computer Science Department, Stanford University, 1973. Google Scholar
  21. Bernhard H Korte and Jens Vygen. Combinatorial optimization. Springer, third edition, 2006. Google Scholar
  22. Eugene L Lawler. Matroid intersection algorithms. Mathematical Programming, 9(1):31-56, 1975. Google Scholar
  23. Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In the 56th Annual Symposium on Foundations of Computer Science (FOCS2015), pages 1049-1065. IEEE, 2015. Google Scholar
  24. Crispin St John Alvah Nash-Williams. An application of matroids to graph theory. In Theory of Graphs - International Symposium - Théorie des graphes - Journées internationales d'étude Rome, pages 263-265, 1966. Google Scholar
  25. Huy L Nguyen. A note on cunningham’s algorithm for matroid intersection, 2019. URL: https://arxiv.org/abs/1904.04129.
  26. Christopher Price. Combinatorial algorithms for submodular function minimization and related problems. Master’s thesis, University of Waterloo, 2015. Google Scholar
  27. Kent Quanrud. Faster exact and approximation algorithms for packing and covering matroids via push-relabel. CoRR, 2023. URL: https://arxiv.org/abs/2303.01478.
  28. Alexander Schrijver et al. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003. Google Scholar
  29. Ta-Wei Tu. Subquadratic weighted matroid intersection under rank oracles. In the 33rd International Symposium on Algorithms and Computation (ISAAC2022), pages 63:1-63:14, 2022. Google Scholar
  30. Andrew Chi-Chih Yao. Monotone bipartite graph properties are evasive. SIAM Journal on Computing, 17(3):517-520, 1988. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact