Intuitive algorithms

Kneis, Joachim; Rossmanith, Peter

doi:HT016136835

Intuitive algorithms = Intuitive Algorithmen

Kneis, Joachim (Author)

2009

Verantwortlichkeitsangabevorgelegt von Joachim Kneis

ImpressumAachen : Publikationsserver der RWTH Aachen University 2009

UmfangVIII, 167 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2009

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Rossmanith, Peter (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2009-07-23

Online
URN: urn:nbn:de:hbz:82-opus-29987
URL: https://publications.rwth-aachen.de/record/51359/files/Kneis_Joachim.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Parametrisierte Komplexität (Genormte SW) ; Theoretische Informatik (Genormte SW) ; Algorithmus (Genormte SW) ; Informatik (frei) ; exakter Algorithmus (frei) ; theoretical computer science (frei) ; exact algorithms (frei) ; parameterized complexity (frei) ; moderately exponential time algorithms (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Wenn wir davon ausgehen, dass die weit verbreitete Annahme P ungleich NP gilt, so können viele wichtige Probleme nicht in polynomieller Zeit gelöst werden. Allerdings gibt es verschiedene Ansätze, dennoch exakte Lösungen für solche Probleme zu berechnen. Besonders hervorzuheben sind hier die Algorithmen mit moderater exponentieller Laufzeit und Algorithmen aus dem Gebiet der parametrisierten Komplexität. In dieser Dissertation präsentieren wir das Konzept der intuitiven Algorithmen, welche in der Regel aus einem der beiden oben genannten Gebieten stammen. Die Grundeigenschaft von intuitiven Algorithmen ist dabei, dass sie einer intuitiven Idee folgen sollen und sonst so einfach wie möglich gehalten sein müssen. Gleichzeitig sollen sie aber Probleme in relativ geringer Zeit exakt lösen. Die geforderte Einfachheit ist bei letzterem natürlich ein Nachteil, zumindest wenn wir Algorithmen in Bezug auf ihre theoretischen Schranken hin analysieren. Allerdings gibt es mehrere Aspekte von intuitiven Algorithmen, die diese Nachteile ausgleichen. Zum einen ist die Laufzeit von intuitiven Algorithmen, sei sie im Allgemeinen auch höher als die von komplizierteren Algorithmen, zumindest auf kleinen Instanzen oft konkurrenzfähig. Auf größeren Instanzen übersteigt aber auch die Laufzeit von komplizierteren Algorithmen jegliche sinnvollen Werte, so dass intuitive Algorithmen in den meisten relevanten Fällen dennoch zu bevorzugen sind. Zudem lassen sich intuitive Algorithmen oft deutlich leichter implementieren, da in theoretischen Algorithmen oft sehr komplexe Operationen versteckt sind. Schließlich sind intuitive Algorithmen aber vor allem ästhetisch zu bevorzugen. Komplizierte Algorithmen sind oft nur deshalb kompliziert, um ihre theoretische Analyse zu vereinfachen oder erst zu ermöglichen. Die zusätzliche Komplexität verrät uns daher oft nur, dass unsere Analysewerkzeuge unzureichend sind, und liefert uns wenig Information darüber, worin die Schwierigkeit des Problems liegt. Ziel dieser Dissertation ist es darzulegen, dass intuitive Algorithmen sowohl obige Eigenschaften aufweisen können und gleichzeitig auch in einer theoretischen Analyse andere Algorithmen übertreffen können. Zu diesem Zweck stellen wir beispielhaft intuitive Algorithmen für verschiedene NP-schwere Probleme vor.

Assuming that P does not equal NP, which is widely believed to be true, many important computational problems are not solvable in polynomial time. However, this does not imply that NP-hard problems are not exactly solvable at all. Both the concepts of moderately exponential time algorithms and parameterized complexity provide tools for solving many of these problems in reasonable time. In this thesis, we introduce the concept of intuitive algorithms. While intuitive algorithms can be either moderately exponential time algorithms or parameterized algorithms, we require that they follow an intuitive idea and are kept as simple as possible. When we analyze algorithms only in terms of a worst case runtime bound, this approach is disadvantageous, as it is sometimes much harder to prove good bounds for simpler algorithms. In some cases, this might even be impossible. However, we will show that there are several aspects of intuitive algorithms that makes the development of such algorithms worthwhile. For example, their runtime is often not as bad as assumed. Especially on small instances, intuitive algorithms often outperform more complex algorithms, because the more complex algorithms tend to unfold their full potential on large instances. However, in practice large instances cannot be solved with exponential time algorithms at all. Furthermore, we often do to not know precise lower bounds on the runtime of exact algorithms. Is is thus hard to decide, whether more complex operations only ease the analysis of a complex algorithm or if such operations really improve the running time. Moreover, intuitive algorithms tend to allow for efficient implementations. This allows us to solve real life instances of surprisingly large size. In contrast to this, implementations of complex algorithms can be rather slow. Finally, intuitive algorithms are often more aesthetic than complex algorithms. Overall, simpler algorithms often tell us more about problems. Throughout this thesis, we will outline that intuitive algorithms can also be competitive when compared to traditional algorithms. To emphasize this, we will present several examples of intuitive algorithms that are either the fastest known algorithms or have only been improved recently.

Fulltext:
PDF