Grenzen von Algorithmenparadigmen
Zusammenfassung der Projektergebnisse
Wir haben untere und obere Schranken für die Leistungsfähigkeit von Greedy-Algorithmen hergeleitet. Im MaxSat-Problem haben wir den ersten Greedy-Algorithmus mit Approximationsfaktor 3/4 entwickelt und für ein realistisches Datenmodell zeigen können, dass deterministische Greedy- Algorithmen den Approximationsfaktor 3/4 nicht erreichen können. Im Matching Problem wurde der bisher beste Approximationsfaktor für die fundamentale MRG-Strategie erreicht. Das Modell dynamischer Branching Programme wurde entwickelt. Dieses Modell ist mächtig genug, um viele wichtige dynamische Programmieralgorithmen auszudrücken: Die Komplexität des Rucksack-Problems wie auch seine Approximationskomplexität kann fast exakt bestimmt werden, exponentielle untere Schranken werden für das TSP-Problem und das Matching Problem entwickelt. Ein klassisches Resultat von Chvátal wird auf ein weitaus mächtigeres Berechnungsmodell verallgemeinert. Überraschenderweise kann für das Subset-Sum Problem gezeigt werden, dass selbst mächtigste Path-Pruning Regeln das Defizit lokaler Verzweigungsregeln nicht wettmachen können. Die Approximationskomplexität von Cutting-Plane Beweisen wird untersucht und exponentielle untere Schranken werden nachgewiesen. Andererseits musste die Hoffnung auf exponentielle untere Schranken für das Clique-Problem enttäuscht werden, zumindest wenn konventionelle Kommunikationsargumente benutzt werden.
Projektbezogene Publikationen (Auswahl)
-
Bounds on greedy algorithms for MAX SAT. In ESA, pages 37–48, 2011
M. Poloczek
-
Randomized variants of Johnson’s algorithm for MAX SAT. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 656–663, 2011
M. Poloczek and G. Schnitger
-
Yet harder knapsack problems. Theor. Comput. Sci., 412(45):6351– 6358, 2011
S. Jukna and G. Schnitger
-
Cutting planes cannot approximate some integer programs. Oper. Res. Lett., 40(4):272–275, 2012
S. Jukna and G. Schnitger
-
Randomized greedy algorithms for the maximum matching problem with new analysis. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 708–717, 2012
M. Poloczek and M. Szegedy
-
Limitations of incremental dynamic programming. Algorithmica, 2013
S. Jukna