Showing cs.DSShow all
3 papers · 1 filter
cs.DS2022
On the Impossibility of Decomposing Binary Matroids
Marilena Leichter, Benjamin Moseley, Kirk Pruhs
We show that there exist -colorable matroids that are not -decomposable when and are constants. A matroid is -decomposable, if its ground set of elements c…
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…