de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

A Compact Linear Program for Testing Optimality of Perfect Matchings

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45666

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44373

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte 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: http://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.