Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Constructing Extended Formulations from Reflection Relations

Kaibel, V., & Pashkovich, K. (2011). Constructing Extended Formulations from Reflection Relations. In Integer Programming and Combinatoral Optimization (pp. 287-300).

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Kaibel, V.1, Autor
Pashkovich, Kanstantsin1, 2, Autor           
Affiliations:
1Otto-von-Guericke-Universität Magdeburg, External Organizations, ou_1738156              
2International Max Planck Research School (IMPRS), Max Planck Institute for Dynamics of Complex Technical Systems, Max Planck Society, ou_1738143              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: There are many examples of optimization problems whose associated polyhedra can be described much nicer, and with way less inequalities, by projections of higher dimensional polyhedra than this would be possible in the original space. However, currently not many general tools to construct such extended formulations are available. In this paper, we develop a framework of polyhedral relations that generalizes inductive constructions of extended formulations via projections, and we particularly elaborate on the special case of reflection relations. The latter ones provide polynomial size extended formulations for several polytopes that can be constructed as convex hulls of the unions of (exponentially) many copies of an input polytope obtained via sequences of reflections at hyperplanes. We demonstrate the use of the framework by deriving small extended formulations for the G-permutahedra of all finite reflection groups G (generalizing both Goeman's extended formulation of the permutahedron of size O(n log n) and Ben-Tal and Nemirovski's extended formulation with O(k) inequalities for the regular 2^k-gon) and for Huffman-polytopes (the convex hulls of the weight-vectors of Huffman codes). © Springer, Part of Springer Science+Business Media [accessed 2014 January 31st]

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2011
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 569909
DOI: 10.1007/978-3-642-20807-2_23
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Integer Programming and Combinatoral Optimization
Genre der Quelle: Buch
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 287 - 300 Identifikator: -

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 6655 Artikelnummer: - Start- / Endseite: - Identifikator: -