Design of approximation algorithms for scheduling on unrelated machines

• Applicant: Professor Dr. Klaus Jansen
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 197234132

• Final Report Year: 2020

Final Report Abstract

Durch das Erlauben von geringfügig schlechteren Lösungen lassen sich Probleme, für die es sonst nur langsame Algorithmen gibt, auch effizient lösen. Solche Verfahren nennen sich Approximationsalgorithmen. Schedulingprobleme mit heterogenen Maschinen zählen zu besonders schwierigen Problemen. Fundamentale Fragen wie, welche Lösungsqualität von einem effizienten Algorithmus noch garantiert werden kann, sind noch nicht abschließend geklärt. Es wurden im Rahmen des Projektes Algorithmen für verschiedene verwandte Probleme entwickelt und analysiert. So konnten wir zum ersten mal zeigen, dass für das RESTRICTED ASSIGNMENT Problem ein Algorithmus mit Approximationsrate besser als 2 und quasi-polynomieller Laufzeit existiert. Im RESTRICTED ASSIGNMENT Problem gilt es eine Menge von Jobs auf Maschinen zu verteilen. Die Ausführungszeit der Jobs ist hierbei abhängig von der zugeordneten Maschine. Es ist hierbei sogar möglich, im Rahmen des RESTRICTED ASSIGNMENT Problems, dass Jobs für bestimmte Maschinen unzulässig sind und diesen nicht zugeordnet werden dürfen. Dabei soll der Makespan minimiert werden, das heißt die maximale Summe von Jobs die sich auf derselben Maschine befinden. Die genaue Rate unseres Algorithmus beläuft sich hier auf 11/6 + 𝜀 ≈ 1,833 + 𝜀, wobei 𝜀 > 0 beliebig gewählt werden kann (mit Einfuss auf die Laufzeit). Die Laufzeit wird durch 𝑛𝑂(1/𝜀 log 𝑛) beschränkt und ist somit asymptotisch wesentlich geringer als bei exponentiellen Algorithmen (z.B. 2𝑛 ). Dies kann auch als wichtiges Indiz für die Existenz eines Polynomialzeit-Algorithmus mit solcher Lösungsqualität gedeutet werden. Ein solcher Algorithmus hätte eine Laufzeit der Form 𝑛𝐶 für eine konstante 𝐶. Dies verbleibt eine wichtige offene Frage. Als wichtiges Werkzeig für das Lösen derartiger Probleme haben wir das Konfigurations-LP intensiv untersucht. Diese LP Relaxierung kann genutzt werden, um Approximationsalgorithmen zu konstruieren. Dies ist aber nur möglich sofern der Integrality Gap gering ist. Wir konnten bessere Schranken für diesen Integrality Gap in zwei Problemen zeigen und ebnen so den Weg für bessere Approximationsalgorithmen. Zum einen haben wir bewiesen, das der Integrality Gap für das RESTRICTED SANTA CLAUS Problem höchstens 3 + 5/6 ≈ 3,833 ist. Dieses Problem entspricht dem RESTRICTED ASSIGNMENT Problem, jedoch wird das Minimum maximiert. Zum anderen konnten wir im GRAPH BALANCING Problem eine Schranke von 1,749 zeigen und somit eine lange bestehende Rate von 1,75 verbessern. GRAPH BALANCING ist der Fall des Restricted Assignment Problems, bei dem jeder Job auf genau zwei Maschinen erlaubt ist. Neben den positiven Resultaten konnten wir für gewisse Probleme auch Algorithmen ausschließen. Es war lange offen, ob es für das Restricted Assignment Problem einen (1 + 𝜀)-Approximationsalgorithmus (für alle 𝜀 > 0) in Polynomialzeit gibt, wenn die erlaubten Maschinenmengen für die Jobs eine Intervallstruktur aufweisen. Einen solchen Algorithmus (und verwandte Fragestellungen) konnten wir jedoch als NP-schwer und somit hoffnungslos identifizieren.

Publications

• „Estimating The Makespan of The Two-Valued Restricted Assignment Problem“. In: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Bd. 53. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016, 24:1–24:13. Algorithmica (Volume 80,2018 , pages 1357-1382)
  K. Jansen, K. Land und M. Maack
  
• „A Quasi-Polynomial Approximation for the Restricted Assignment Problem“. In: Proceedings of the 19th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2017), Waterloo, ON, Canada, June 26-28, 2017
  K. Jansen und L. Rohwedder
  
• „On the Configuration-LP of the Restricted Assignment Problem“. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, January 16-19. 2017, S. 2670– 2678
  K. Jansen und L. Rohwedder
  
• „Structural Parameters for Scheduling with Assignment Restrictions“. In: Algorithms and Complexity (CIAC 2017). Springer International Publishing, 2017, S. 357–368. Theoretical Computer Science (Volume 844, 2020, Pages 154-170)
  K. Jansen, M. Maack und R. Solis-Oba
  
• „A note on the integrality gap of the configuration LP for restricted Santa Claus“. In: CoRR abs/1807.03626 (2018)
  K. Jansen und L. Rohwedder
  
• „Compact LP Relaxations for Allocation Problems“. In: 1st Symposium on Simplicity in Algorithms (SOSA 2018), January 7-10, 2018, New Orleans, LA, USA. 2018, 11:1–11:19
  K. Jansen und L. Rohwedder
  
• „Local Search Breaks 1.75 for Graph Balancing“. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), July 9-12, 2019, Patras, Greece. 2019, 74:1–74:14
  K. Jansen und L. Rohwedder
  
• „Inapproximability Results for Scheduling with Interval and Resource Restrictions“. In: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Bd. 154. 2020, 5:1–5:18
  M. Maack und K. Jansen