It is a longstanding open problem whether there exists a polynomial size description of the perfect matching polytope. We give a partial answer to this question by proving the following result. The polyhedron defined by the constraints of the perfect matching polytope which are active at a given perfect matching can be obtained as the projection of a compact polyhedron. Thus there exists a compact linear program which is unbounded if and only if the perfect matching is not optimal with respect to a given edge weight. This result provides a simple reduction of the maximum weight perfect matching problem to compact linear programming.
A compact linear program for testing optimality of perfect matching
Ventura P;
2003
Abstract
It is a longstanding open problem whether there exists a polynomial size description of the perfect matching polytope. We give a partial answer to this question by proving the following result. The polyhedron defined by the constraints of the perfect matching polytope which are active at a given perfect matching can be obtained as the projection of a compact polyhedron. Thus there exists a compact linear program which is unbounded if and only if the perfect matching is not optimal with respect to a given edge weight. This result provides a simple reduction of the maximum weight perfect matching problem to compact linear programming.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
