LIPIcs.ESA.2021.62.pdf
- Filesize: 0.8 MB
- 13 pages
Document
An Efficient Reduction of a Gammoid to a Partition Matroid
Authors
-
Part of:
Volume:
29th Annual European Symposium on Algorithms (ESA 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-08-31
Cite As Get BibTex
Marilena Leichter, Benjamin Moseley, and Kirk Pruhs. An Efficient Reduction of a Gammoid to a Partition Matroid. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 62:1-62:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.62
Abstract
Our main contribution is a polynomial-time algorithm to reduce a k-colorable gammoid to a (2k-2)-colorable partition matroid. It is known that there are gammoids that can not be reduced to any (2k-3)-colorable partition matroid, so this result is tight. We then discuss how such a reduction can be used to obtain polynomial-time algorithms with better approximation ratios for various natural problems related to coloring and list coloring the intersection of matroids.
Subject Classification
ACM Subject Classification
- Theory of computation → Network optimization
Keywords
- Matroid
- Gammoid
- Reduction
- Algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Ron Aharoni and Eli Berger. The intersection of a matroid and a simplicial complex. Transactions of the American Math Society, 2006.
-
Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice hall, 1993.
-
Kristóf Bérczi, Tamás Schwarcz, and Yutaro Yamaguchi. List colouring of two matroids through reduction to partition matroids. arXiv preprint arXiv:1911.10485, 2019.
-
Jack Edmonds. Minimum partition of a matroid into independent subsets. Journal of Research of the National Bureau of Standards, 69B:67–72, 1965.
-
Sungjin Im, Benjamin Moseley, and Kirk Pruhs. The matroid intersection cover problem. Operations Research Letters, 49(1):17-22, 2020.
-
Jon M. Kleinberg. Single-source unsplittable flow. In Symposium on Foundations of Computer Science, pages 68-77, 1996.
-
Nabil Hassan Mustafa and Saurabh Ray. PTAS for geometric hitting set problems via local search. In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 17-22, 2009.
-
James Oxley. Matroid Theory. Oxford graduate texts in mathematics. Oxford University Press, 2006.
-
Paul D Seymour. A note on list arboricity. Journal of Combinatorial Theory, Series B, 72(1):150-151, 1998.
-
Vijay Vazirani. Approximation Algorithms. Springer-Verlag, 2001.
-
David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.