Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2010 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Exact Exponential Algorithms

verfasst von: Fedor V. Fomin, Dieter Kratsch

Verlag: Springer Berlin Heidelberg

Buchreihe : Texts in Theoretical Computer Science. An EATCS Series

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

For a long time computer scientists have distinguished between fast and slow algo rithms. Fast (or good) algorithms are the algorithms that run in polynomial time, which means that the number of steps required for the algorithm to solve a problem is bounded by some polynomial in the length of the input. All other algorithms are slow (or bad). The running time of slow algorithms is usually exponential. This book is about bad algorithms. There are several reasons why we are interested in exponential time algorithms. Most of us believe that there are many natural problems which cannot be solved by polynomial time algorithms. The most famous and oldest family of hard problems is the family of NP complete problems. Most likely there are no polynomial time al gorithms solving these hard problems and in the worst case scenario the exponential running time is unavoidable. Every combinatorial problem is solvable in ?nite time by enumerating all possi ble solutions, i. e. by brute force search. But is brute force search always unavoid able? De?nitely not. Already in the nineteen sixties and seventies it was known that some NP complete problems can be solved signi?cantly faster than by brute force search. Three classic examples are the following algorithms for the TRAVELLING SALESMAN problem, MAXIMUM INDEPENDENT SET, and COLORING.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
In this introductory chapter we start with a preliminary part and present then two classical exact algorithms breaking the triviality barrier. The first one, from the nineteen sixties, is the dynamic programming algorithm of Bellman, Held and Karp to solve the Travelling Salesman problem [16, 17, 111]. The second is a branching algorithm to compute a maximum independent set of a graph. The main idea of this algorithm can be traced back to the work of Miller and Muller [155] and Moon and Moser [161] from the nineteen sixties.
Fedor V. Fomin, Dieter Kratsch
Chapter 2. Branching
Abstract
Branching is one of the basic algorithmic techniques for designing fast exponential time algorithms. It is safe to say that at least half of the published fast exponential time algorithms are branching algorithms. Furthermore, for many NP-hard problems the fastest known exact algorithm is a branching algorithm. Many of those algorithms have been developed during the last ten years by applying techniques like Measure & Conquer, quasiconvex analysis and related ones.
Fedor V. Fomin, Dieter Kratsch
Chapter 3. Dynamic Programming
Abstract
Dynamic programming is one of the basic algorithmic techniques. Contrary to branching algorithms, dynamic programming is of great importance for designing polynomial time algorithms as well as for designing exponential time algorithms. The main idea of dynamic programming is to start by solving small or trivial instances and then gradually resolving larger and harder subproblems by composing solutions from smaller subproblems. From this point of view, dynamic programming is quite opposite to branching, where we try to decompose the problem.
Fedor V. Fomin, Dieter Kratsch
Chapter 4. Inclusion-Exclusion
Abstract
Inclusion-exclusion is a fascinating technique used in the design of fast exponential time algorithms. It is based on the inclusion-exclusion principle which is a fundamental counting principle in combinatorics; it allows us to count combinatorial objects in a somewhat indirect way that is applied in particular when direct counting is not possible. This counting principle is the main tool when designing inclusionexclusion algorithms. It seems that this algorithm design paradigm is suited very well to constructing fast exponential time algorithms since it naturally produces exponential time algorithms.
Fedor V. Fomin, Dieter Kratsch
Chapter 5. Treewidth
Abstract
The treewidth of a graph is one of the most fundamental notions in graph theory and graph algorithms. In this chapter, we give several applications of treewidth in exact algorithms.We also provide an exact algorithm computing the treewidth of a graph.
Fedor V. Fomin, Dieter Kratsch
Chapter 6. Measure & Conquer
Abstract
Measure & Conquer is a powerful method used to analyse the running time of branching algorithms. Typically it allows us to achieve running times for branching algorithms that seem hard or even impossible to establish by the simple analysis of branching algorithms studied in Chap. 2. The main difference is that the measure for the size of an instance of a subproblem and thus also the measure for the progress during the branching algorithm’s execution will be chosen with much more freedom.
Fedor V. Fomin, Dieter Kratsch
Chapter 7. Subset Convolution
Abstract
In the first two sections we explain the fundamentals of subset convolution and the fast algorithm to compute it. To obtain a fast subset convolution algorithm one relies on repeated use of dynamic programming, and in particular on the so-called fast zeta transform. In the latter sections we present various algorithmic applications of fast subset convolution. In this chapter the algorithms (may) operate with large numbers and thus we use the log-cost RAM model to analyze their running times.
Fedor V. Fomin, Dieter Kratsch
Chapter 8. Local Search and SAT
Abstract
In Chap. 2, we discuss a branching algorithm for the k-Satisfiability problem. In this chapter we consider more techniques for solving k-SAT. Both techniques are based on performing local search in balls in the Hamming space around some assignments. The first algorithm randomly chooses an assignment and performs a random walk of short length (in Hamming distance) to search for the solution. The second algorithm is deterministic and uses a similar idea; but instead of using a random walk, it finds a covering of the Hamming space by balls of specified radius and performs a search inside these balls.
Fedor V. Fomin, Dieter Kratsch
Chapter 9. Split and List
Abstract
In this chapter we discuss several algorithms based on the following approach. There is a number of efficient algorithms for many problems in P. To apply these algorithms on hard problems, we (exponentially) enlarge the size of a hard problem and apply fast polynomial time algorithm on an input of exponential size. The common way to enlarge the problem is to split the input into parts, and for each part to enumerate (or list) all possible solutions to subproblems corresponding to the part. Then we combine solutions of subproblems to solutions of the input of the original problem by making use of a fast polynomial time algorithm.
Fedor V. Fomin, Dieter Kratsch
Chapter 10. Time Versus Space
Abstract
We have already met different types of exponential algorithms. Some of them use only polynomial space, among them in particular the branching algorithms. On the other hand, there are exponential time algorithms needing exponential space, among them in particular the dynamic programming algorithms. In real life applications polynomial space is definitely preferable to exponential space. However, often a “moderate” usage of exponential space can be tolerated if it can be used to speed up the running time. Is it possible by sacrificing a bit of running time to gain in space? In the first section of this chapter we discuss such an interpolation between the two extremes of space complexity for dynamic programming algorithms. In the second section we discuss an opposite technique to gain time by using more space, in particular for branching algorithms.
Fedor V. Fomin, Dieter Kratsch
Chapter 11. Miscellaneous
Abstract
In this chapter we collect several unrelated results. The algorithm solving the Bandwidth Minimization problem can be seen as a combination of the branching and the dynamic programming techniques. The second section on Branch & Recharge provides a new angle on branching algorithms. The third section gives a brief overview of fundamental results by Impagliazzo, Paturi, and Zane, and the Exponential Time Hypothesis.
Fedor V. Fomin, Dieter Kratsch
Chapter 12. Conclusions, Open Problems and Further Directions
Abstract
We conclude with a number of open problems. Some of them are of a fundamental nature and some of them can serve as starting points for newcomers in the field.
Fedor V. Fomin, Dieter Kratsch
Backmatter
Metadaten
Titel
Exact Exponential Algorithms
verfasst von
Fedor V. Fomin
Dieter Kratsch
Copyright-Jahr
2010
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-16533-7
Print ISBN
978-3-642-16532-0
DOI
https://doi.org/10.1007/978-3-642-16533-7