The Cutting Plane Method is Polynomial for Perfect Matchings

References

• Balas E (1971) Intersection cuts—A new type of cutting planes for integer programming. Oper. Res. 19(1):19–39.Link, Google Scholar
• Balas E (1979) Disjunctive programming. Ann. Discrete Math. 5:3–51.Crossref, Google Scholar
• Balas E, Ceria S, Cornuéjols G (1993) A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Programming 58(1):295–324.Crossref, Google Scholar
• Bunch PR (1997) A simplex based primal-dual algorithm for the perfect b-matching problem—A study in combinatorial optimization algorithm in engineering. Unpublished doctoral dissertation, Purdue University, Lafayette.Google Scholar
• Chandrasekaran K, Végh LA, Vempala SS (2015) A half-integral algorithm for minimum weight matching. Working paper, University of Illinois at Urbana–Champaign.Google Scholar
• Chvátal V (1973) Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4(4):305–337.Crossref, Google Scholar
• Cook W, Kannan R, Schrijver A (1990) Chvátal closures for mixed integer programming problems. Math. Programming 47(1):155–174.Crossref, Google Scholar
• Cornuéjols G, Li Y (2001) Elementary closures for integer programs. Oper. Res. Lett. 28(1):1–8.Crossref, Google Scholar
• Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. Oper. Res. 2(4):393–410.Link, Google Scholar
• Edmonds J (1965) Maximum matching and a polyhedron with 0, 1-vertices. J. Res. National Bureau of Standards 69(1–2):125–130.Crossref, Google Scholar
• Edmonds J (1965) Paths, trees, and flowers. Canadian J. Math. 17(3):449–467.Crossref, Google Scholar
• Fischetti M, Lodi A (2007) Optimizing over the first Chvátal closure. Math. Programming 110(1):3–20.Crossref, Google Scholar
• Gomory RE (1958) Outline of an algorithm for integer solutions to linear programs. Bull. Amer. Math. Soc. 64(5):275–278.Crossref, Google Scholar
• Gomory RE (1960) Solving linear programs in integers. Proc. Symposia Appl. Math., Vol. 10, 211–215.Google Scholar
• Gomory RE (1963) An algorithm for integer solutions to linear programs. Recent Adv. Math. Programming, 269–302.Google Scholar
• Grötschel M, Holland O (1985) Solving matching problems with linear programming. Math. Programming 33(3):243–259.Crossref, Google Scholar
• Grötschel M, Lovász L, Schrijver A (1988) Geometric Algorithms and Combinatorial Optimization (Springer, Berlin).Crossref, Google Scholar
• Kannan R (1987) Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3):415–440.Link, Google Scholar
• Lovász L, Plummer MD (2009) Matching Theory (AMS, Providence, RI).Crossref, Google Scholar
• Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1:166–190.Crossref, Google Scholar
• Miller DL, Pekny JF (1995) A staged primal-dual algorithm for perfect b-matching with edge capacities. ORSA J. Comput. 7(3):298–320.Link, Google Scholar
• Nemhauser G, Wolsey L (1999) Integer and Combinatorial Optimization (John Wiley & Sons, New York).Google Scholar
• Nemhauser GL, Wolsey LA (1990) A recursive procedure to generate all cuts for 0-1 mixed integer programs. Math. Programming 46(1):379–390.Crossref, Google Scholar
• Padberg MW, Rao MR (1982) Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7(1):67–80.Link, Google Scholar
• Schrijver A (1998) Theory of Linear and Integer Programming (John Wiley & Sons, New York).Google Scholar
• Schrijver A (2003) Combinatorial Optimization—Polyhedra and Efficiency (Springer, Berlin).Google Scholar
• Sherali HD, Adams WP (1994) A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discrete Appl. Math. 52(1):83–106.Crossref, Google Scholar
• Trick MA (1987) Networks with additional structured constraints. Unpublished doctoral dissertation, Georgia Institute of Technology, Atlanta.Google Scholar