3 papers
cs.DS2021
An Efficient Reduction of a Gammoid to a Partition Matroid
Marilena Leichter, Benjamin Moseley, Kirk Pruhs
Our main contribution is a polynomial-time algorithm to reduce a -colorable gammoid to a -colorable partition matroid. It is known that there are gammoids that can not b…
cs.DS2021
A Stronger Impossibility for Fully Online Matching
Alexander Eckl, Anja Kirschbaum, Marilena Leichter +1
We revisit the fully online matching model (Huang et al., J.\ ACM, 2020), an extension of the classic online matching model due to Karp, Vazirani, and Vazirani (STOC 1990), which h…
math.CO2017
Locally Searching for Large Induced Matchings
Maximilian Fürst, Marilena Leichter, Dieter Rautenbach
It is an easy observation that a natural greedy approach yields a -factor approximation algorithm for the maximum induced matching problem in -regular graph…