This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  ALL, with author Eisenbrand F., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 573  (Previous )  

Eisenbrand F., Paolo Ventura

A compact linear program for testing optimality of perfect matchings

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. Keywords: Matching, linear programming compact linear programming. Key words: stable set polytope, graph composition, claw-free graphs.