Intuitive algorithms

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.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2009

Author dc:creator

• Kneis, Joachim

Contributors dc:contributor

• Rossmanith, Peter

• info:eu-repo/classification/ddc/004
• Parametrisierte Komplexität
• Theoretische Informatik
• Algorithmus
• Informatik
• exakter Algorithmus
• theoretical computer science
• exact algorithms
• parameterized complexity
• moderately exponential time algorithms

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-113660%22

OAI record oai:identifier

https://publications.rwth-aachen.de/oai2d?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Apublications.rwth-aachen.de%3A51359