DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2021.62

An Efficient Reduction of a Gammoid to a Partition Matroid

Authors: Marilena Leichter, Benjamin Moseley, and Kirk Pruhs

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{leichter_et_al:LIPIcs.ESA.2021.62,
  author =	{Leichter, Marilena and Moseley, Benjamin and Pruhs, Kirk},
  title =	{{An Efficient Reduction of a Gammoid to a Partition Matroid}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{62:1--62:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.62},
  URN =		{urn:nbn:de:0030-drops-146432},
  doi =		{10.4230/LIPIcs.ESA.2021.62},
  annote =	{Keywords: Matroid, Gammoid, Reduction, Algorithms}
}

Search Results

Documents authored by Leichter, Marilena

An Efficient Reduction of a Gammoid to a Partition Matroid

Abstract

Cite as

Thanks for your feedback!

Could not send message