Showing 2021Show all
2 papers · 1 filter
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…