Reducing Matching to Polynomial Size Linear Programming
Chinese postmancompact linear programmatchingminimum mean cycle problemspolynomial algorithmsystems of linear inequalities
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Linear programming (90C05) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Systems of linear inequalities that fully describe the feasible solutions of a combinatorial optimization problem (P) are called compact if they use a polynomial number of variables and a polynomial number of inequalities. If such a system is known, problem (P) can be solved in polynomial time by use of any polynomial algorithm for linear programming. This paper addresses the well-known matching problem over general graphs. It is shown that the Chinese postman problem reduces to a sequence of \(O(m^ 2\log n)\) minimum mean cycle problems. This latter problem is shown to possess a linear programming formulation of polynomial size. Thus, a polynomial algorithm for matching is obtained whose only non- trivial operation consists in solving a linear program of polynomial size. A combinatorial algorithm for finding minimum mean cycles in undirected graphs is also given.
- Matching: A well-solved class of integer linear programs
- A compact linear program for testing optimality of perfect matchings.
- Solving matching problems with linear programming
- A new algorithm for general matching problems using network flow subproblems
- Polynomial size linear programs for problems in \textsc{P}
- Minimum mean cycle problem in bidirected and skew-symmetric graphs
- A compact linear program for testing optimality of perfect matchings.
- Edmonds, matching and the birth of polyhedral combinatorics
- Polynomial size linear programs for problems in \textsc{P}
- Solving matching problems with linear programming
- Linear Systems for Constrained Matching Problems
- scientific article; zbMATH DE number 59833 (Why is no real title available?)
- Matching: A well-solved class of integer linear programs
- Using matching to detect infeasibility of some integer programs
- Maximum matching and linear programming in fixed-point logic with counting
- Extended formulations in combinatorial optimization
- Extended formulations in combinatorial optimization
- Matching 2-lattice polyhedra: Finding a maximum vector
- On cuts and matchings in planar graphs
- Two strongly polynomial cut cancelling algorithms for minimum cost network flow
- A note on the core of 2-matching games
This page was built for publication: Reducing Matching to Polynomial Size Linear Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4277507)