Entwicklung und Analyse effizienter Algorithmen zur ganzzahligen linearen Optimierung über Polyedern mit zugrunde liegender submodularer Struktur
Final Report Abstract
Das Kernziel des Projekts lag in der Entwicklung und Analyse einfacher und effizienter Algorithmen für kombinatorische Packungs- und Überdeckungsprobleme unter Ausnutzung zugrunde liegender sub- und supermodularer Strukturen. Den Ausgangspunkt bildete das auf Alan Hoffman zuruckgehende Konzept der Verbandspolyeder. Bereits in den 70er Jahren wurde die Existenz ganzzahliger Optimallösungen für die Verbandspolyedern entsprechenden primal-dualen linearen Programme bei beliebigen Kostenfunktionen nachgewiesen. Dieses weit umfassende Existenzresultat wird allerdings nur in einzelnen Spezialfällen von entsprechenden kombinatorischen primal-dualen Algorithmen begleitet. Im Rahmen dieses Projekts konnten wir einen primal-dualen Algorithmus für binäre Verbandspolyeder im allgemeinen entwickeln und damit die wichtigste im Antrag formulierte Frage positiv beantworten. Strukturelle Einsichten hinsichtlich effizienter Entkreuzungsmethoden basierend auf submodularen Strukturen konnten wir zur Entwicklung und Analyse bei weiteren Forschungsgebieten erfolgreich einsetzen, wie z.B. Untersuchungen zu Existenz und Güte von Gleichgewichten bei Auslastungsspielen, beim verallgemeinerten Netzwerkdesign mit Gradbeschrankungen, bei Verallgemeinerungen abstrakter, submodularer und dynamischer Flüsse im allgemeinen und in planaren Graphen, sowie zur Maximierung submodularer Funktionen auf dem Gitterverband und bei Netzwerkdesignproblemen mit binaren Budgetbeschränkungen.
Publications
- (2017) Matroids Are Immune to Braess’ Paradox. Mathematics of OR (Mathematics of Operations Research) 42 (3) 745–761
Fujishige, Satoru; Goemans, Michel X.; Harks, Tobias; Peis, Britta; Zenklusen, Rico
(See online at https://doi.org/10.1287/moor.2016.0825) - A Primal-Dual Algorithm for Weighted Abstract Cut Packing. Proceedings of the 15th Workshop on Integer Programming and Combinatorial Optimization (IPCO), 2011, pp. 324-333
S. Thomas McCormick and Britta Peis
- On generalizations of network design problems with degree bounds. Math. Program., 141(1-2):479-506, 2013
Nikhil Bansal, Rohit Khandekar, Jochen Könemann, Viswanath Nagarajan, and Britta Peis
- Resource Competition on Integral Polymatroids. Proceedings of WINE (2014), pp. 189-202
Tobias Harks, Max Klimm, Britta Peis
(See online at https://doi.org/10.1007/978-3-319-13129-0_14) - Submodular Function Maximization on the Bounded Integer Lattice. Proceedings of International Workshop on Approximation and Online Algorithms (WAOA), 2016, pp. 133-144
Corinna Gottschalk and Britta Peis
(See online at https://doi.org/10.1007/978-3-319-28684-6_12) - Greedy Oriented Flows. Algorithmica (2017)
Ulrich Faigle, Walter Kern, Britta Peis
(See online at https://dx.doi.org/10.1007/s00453-017-0306-4)
