Grenzen von Algorithmenparadigmen

• Applicant: Professor Dr. Georg Schnitger
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 170530402

• Final Report Year: 2013

Final Report Abstract

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.

Publications

• 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
  (See online at https://doi.org/10.1016/j.orl.2012.03.008)
• 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
  (See online at https://doi.org/10.1007/s00453-013-9747-6)