Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  A Compact Linear Program for Testing Optimality of Perfect Matchings

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

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2BEA-A Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-C0EC-A
Genre: Zeitschriftenartikel

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Ventura, Paolo1, Autor           
Eisenbrand, Friedrich2, Autor           
Affiliations:
1Machine Learning, MPI for Informatics, Max Planck Society, ou_1116552              
2Discrete Optimization, MPI for Informatics, Max Planck Society, ou_1116548              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2004-07-012003
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 201880
Anderer: Local-ID: C1256BDD00205AD6-4A3D46B34DD76218C1256D09002D6698-VE2003
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Operations Research Letters
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Amsterdam : North-Holland
Seiten: - Band / Heft: 31 Artikelnummer: - Start- / Endseite: 429 - 434 Identifikator: ISSN: 0167-6377
CoNE: https://pure.mpg.de/cone/journals/resource/954925483661