Matthias Walter

Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs

  • Matthias Walter
    • Categories (Mixed) Integer Nonlinear Programming, Polyhedra Tags

    We consider, for complete bipartite graphs, the convex hulls of characteristic vectors of matchings, extended by a binary number indicating whether the matching contains two specific edges. This polytope is associated to the quadratic matching problem with a single linearized quadratic term. We provide a complete irredundant inequality description, which settles a conjecture by Klein … Read more

    Extended Formulations for Independence Polytopes of Regular Matroids

  • Volker Kaibel
  • Jon Lee
  • Matthias Walter
  • Stefan Weltge
    • Categories Linear Programming, Polyhedra Tags , , ,

    We show that the independence polytope of every regular matroid has an extended formulation of size quadratic in the size of its ground set. This generalizes a similar statement for (co-)graphic matroids, which is a simple consequence of Martin’s extended formulation for the spanning-tree polytope. In our construction, we make use of Seymour’s decomposition theorem … Read more