LP hardness of approximation for polynomial-time solvable problems

@misc{lemmata:2610.00004,
  title        = {LP hardness of approximation for polynomial-time solvable problems},
  author       = {Sebastian Pokutta},
  howpublished = {Lemmata Repository, lemmata:2610.00004, \url{https://lemmata.iol.berlin/abs/2610.00004}},
  year         = {2026},
  url          = {https://lemmata.iol.berlin/abs/2610.00004},
  note         = {Version a9429cb9cbf5; formal statements checked in Lean 4}
}

Abstract. We give concrete reductions from shifted matching matrices to approximate LP formulations for four polynomial-time solvable problems: metric minimum-cost perfect matching, minimum-cost T-join, minimum odd cut, and minimum-cost odd-red bipartite perfect matching. The first three yield exponential lower bounds for every fixed approximation factor from the shifted matching-matrix rank theorem of Braun and Pokutta. For parity matching, Lean also proves the new charging argument and finite shifted-rank bound from explicit partition and entropy hypotheses of Jia, Svensson, and Yuan. The concrete constructions, optimum identities, and transfers to formulation size are formalized; the earlier source theorems and the existence of affine Farkas certificates remain external.

Status¶

All formal results are kernel-checked with Lean v4.35.0. What “checked” means.

View the full entry → · category: Optimization