Reducing Matching to Polynomial Size Linear Programming

From MaRDI portal





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.











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)