1 Search Results for "Leichter, Marilena"

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-dev.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}
}
  • Refine by Author
  • 1 Leichter, Marilena
  • 1 Moseley, Benjamin
  • 1 Pruhs, Kirk

  • Refine by Classification
  • 1 Theory of computation → Network optimization

  • Refine by Keyword
  • 1 Algorithms
  • 1 Gammoid
  • 1 Matroid
  • 1 Reduction

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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