Erweiterte Formulierungen der nächsten Generation
Zusammenfassung der Projektergebnisse
Erweiterte Formulierungen sind ein bekanntes Konzept, um diskrete Optimierungsprobleme als lineare oder gemischt-ganzzahlige Programme auf kompakte Weise zu formulieren. Das Ziel dieses Projekts bestand darin, die dahinterliegende Theorie aus verschiedenen Perspektiven zu erweitern und neue Anwendungen zu entwickeln. Unsere Hauptergebnisse sind die folgenden. • Wir konstruieren eine Familie von Gittern, deren Voronoi-Zellen keine polynomiell großen (linearen bzw. semidefiniten) erweiterten Formulierungen zulassen. Zudem konstruieren wir polynomiell große erweiterte Formulierungen für Voronoi-Zellen sogenannter Root Lattices, eine reiche Familie von Gittern, die viele Extremalbeispiele enthält. Kompakte Darstellungen von Voronoi-Zellen von Lattices können in Algorithmen fur Probleme wie das Closest Vector Problem genutzt werden. • Wir konstruieren Graphen mit n Knoten, für die jede polynomiell große Formulierung des Stable-Set-Problems als gemischt-ganzzahliges Programm Ω(n/ log2 n) ganzzahlige Variablen benötigt. Unsere Schranke ist im Wesentlichen optimal in dem Sinne, dass übliche Formulierungen O(n) ganzzahlige Variablen verwenden. Die bisher beste untere √ Schranke war Ω( n/ log n). Unsere Ergebnisse implizieren ein analoges Ergebnis für das Rucksackproblem (Knap-sack problem). • Wir konstruieren polynomiell große erweiterte Formulierungen Feedback Vertex Set Problem, mit einem Integrality Gap von höchstens 2. Fur das Problem existierten bereits kombinatorische und primal-duale 2-Approximationen, allerdings war bisher keine LP-Relaxierung bekannt, deren Integrality Gap höchstens 2 und die effizient lösbar ist. Im Rahmen dieses Projekts haben unsere Diskussionen auch zu weiteren Ergebnissen in der Theorie der ganzzahligen Programmierung geführt: • Wir konstruieren n-dimensionale gitterpunktfreie Simplizes mit einer Gitterbreite von 2n− o(n), was zu einer neuen unteren Schranke für die Flatness-Konstante führt. Die bisher beste untere Schranke lag bei 1.138n. Die Flatness-Konstante ist die bestmögliche Schranke im Flatness-Theorem, und ihr Wert beeinflusst die Laufzeit mehrerer Algorithmen für die ganzzahlige Programmierung. • Wir stellen einen Polynomialzeit-Algorithmus zur Lösung ganzzahliger Programme vor, deren Koeffizientenmatrix höchstens zwei Nichtnullen pro Zeile aufweist und bei dem alle Subdeterminanten durch eine Konstante begrenzt sind. Insbesondere leiten wir einen polynomiellen Algorithmus für das Stabile-Mengen-Problem in der Familie der Graphen mit begrenzter Odd Cycle Packing Number her. Für das letztgenannte Problem war vor unserer Arbeit nur ein PTAS bekannt. Unser Hauptergebnis stützt die aktiv diskutierte Vermutung, dass ganzzahlige Programme mit begrenzten Subdeterminanten in Polynomialzeit gelöst werden können.
Projektbezogene Publikationen (Auswahl)
-
Integer programs with bounded subdeterminants and two nonzeros per row. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 13-24. IEEE.
Fiorini, Samuel; Joret, Gwenael; Weltge, Stefan & Yuditsky, Yelena
-
Lattice-Free Simplices with Lattice Width 2d − o(d). Lecture Notes in Computer Science, 375-386. Springer International Publishing.
Mayrhofer, Lukas; Schade, Jamico & Weltge, Stefan
-
Lifts for Voronoi Cells of Lattices. Discrete & Computational Geometry, 70(3), 845-865.
Schymura, Matthias; Seidel, Ina & Weltge, Stefan
-
Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack. Lecture Notes in Computer Science, 379-392. Springer Nature Switzerland.
Schade, Jamico; Sinha, Makrand & Weltge, Stefan
-
Integer programs with bounded subdeterminants and two nonzeros per row. Journal of the ACM, 72(1), 1-50.
Fiorini, Samuel; Joret, Gwenaël; Weltge, Stefan & Yuditsky, Yelena
-
Polyhedral aspects of feedback vertex set and pseudoforest deletion set. Mathematical Programming, 214(1-2), 153-200.
Chandrasekaran, Karthekeyan; Chekuri, Chandra; Fiorini, Samuel; Kulkarni, Shubhang & Weltge, Stefan
