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.
Copyright. All Rights Reserved.