Abstract
Local search vs. LP for Matroid Matching
Jon Lee
University of Michigan
We give a simple local-search based PTAS for classical matroid matching/parity in the oracle model, and we demonstrate that well-studied LP formulation are hopeless for construction of polynomial-time approximations. Joint work
with Maxim Sviridenko and Jan Vondrak.
with Maxim Sviridenko and Jan Vondrak.
No video available