Local search vs. LP for Matroid Matching

Jon Lee
IBM Thomas J. Watson Research Center
Mathematical Sciences

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.

Back to Workshop III: Discrete Optimization