Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
  Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben
Zeitschriftenartikel

A Compact Linear Program for Testing Optimality of Perfect Matchings

MPG-Autoren
/persons/resource/persons45666

Ventura,  Paolo
Machine Learning, MPI for Informatics, Max Planck Society;

/persons/resource/persons44373

Eisenbrand,  Friedrich
Discrete Optimization, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Ventura, P., & Eisenbrand, F. (2003). A Compact Linear Program for Testing Optimality of Perfect Matchings. Operations Research Letters, 31, 429-434.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-000F-2BEA-A
Zusammenfassung
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.