• search hit 1 of 1
Back to Result List

## Amortized Analysis of Exponential Time- and Parameterized Algorithms: Measure & Conquer and Reference Search Trees

### Amortisierte Analyse von exponentialzeit- und parameterisierten Algorithmen: Measure & Conquer und Reference Search Trees

• This work addresses the algorithmic tractability of hard combinatorial problems. Basically, we are considering \NP-hard problems. For those problemsrnwerncan not find a polynomial time algorithm. Several algorithmic approaches already exist which deal with this dilemma. Amongrnthemrnwe find (randomized) approximation algorithms and heuristics. Even though in practice they often work in reasonable time they usually do not return anrnoptimal solution. If we constrain optimality then there are only two methods which suffice for this purpose: exponential time algorithms andrnparameterized algorithms. In the first approach we seek to design algorithms consuming exponentially many steps who are more clever than some trivialrnalgorithm (whornsimply enumerates all solution candidates).rnTypically, the naive enumerative approach yields an algorithm with run time $\Oh^*(2^n)$. So, the general task is to construct algorithms obeying a run time of rnthe form $\Oh^*(c^n)$ where $c<2$.rn The second approach considers an additional parameter $k$ besides the input size $n$. This parameter shouldrnprovide more information about the problem and cover a typical characteristic. The standard parameterization is to see $k$ as an upper (lower, resp.)rnbound on the solution size in case of a minimization (maximization, resp.) problem. Then a parameterized algorithm should solve the problem in time $f(k)\cdot n^\beta$rnwhere $\beta$ is a constant and $f$ is independent of $n$. In principle this method aims to restrict the combinatorial difficulty of the problem tornthe parameter $k$ (if possible). The basic hypothesis is that $k$ is small with respect to the overall input size.rnIn both fields a frequent standard technique is the design of branching algorithms. These algorithms solve the problem by traversing the solutionrnspace in a clever way. They frequently select an entity of the input and create two new subproblems, one where this entity is considered as part ofrnthernfuture solution and another one where it is excluded from it. Then in both cases by fixing this entity possibly other entities will be fixed. If so then therntraversedrnnumber of possible solution is smaller than the whole solution space. The visited solutions can be arranged like a search tree. To estimate thernrun time of such algorithms there is need for a method to obtain tight upper bounds on the size of the search trees. In the field of exponential timernalgorithms a powerful technique called Measure&Conquer has been developed for this purpose. It has been applied successfully to manyrnproblems, especially to problems where other algorithmic attacks could not break the trivial run time upper bound. rnOn the other hand in the field of parameterized algorithms Measure&Conquer is almost not known. This piece of work will presentrnexamples where this technique can be used in this field. It also will point out what differences have to be made in order to successfully applyrnthe technique. Further, exponential time algorithms for hard problems where Measure&Conquer is applied are presented. Another aspect is thatrna formalization (and generalization) of the notion of a search tree is given. It is shown that for certain problems such a formalization is extremely useful.rn
• Diese Arbeit diskutiert die algorithmische Handhabbarkeit schwieriger kombinatorischer Probleme. Grundsätzlich betrachten wir NP-schwere Probleme. rnFür diese Art von Problemen ist es unmöglich Polynomialzeit-Algorithmen zu finden. Mehrere algorithmische Ansätzernexistieren bereits, um diesem Dilemma zu entkommen. Darunter befinden sich (randomisierte) Approximations-Algorithmen und Heuristiken. Obwohl diesernin annehmbarer Zeit eine Lösung liefern, ist diese im allgemeinen nicht optimal. Falls wir Optimalität voraussetzen dann gibt es nur zwei Methodenrndie dies gewährleisten: Exponentialzeit-Algorithmen und parameterisierte Algorithmen. Der erste Ansatz versucht Algorithmenrnzu finden, die intelligenter handeln als ein trivialer Algorithmus, der einfach alle Lösungskandidaten aufzählt. Typischerweise benötigt solchrnein naiver Aufzählungsansatz eine Laufzeit von $\Oh^*(2^n)$. Deshalb ist die prinzipielle Aufgabe Algorithmen zu entwerfen, die eine Laufzeit der Formrn$\Oh^*(c^n)$, wobei $c<2$ gilt, garantieren. rnDer zweite Ansatz betrachtet einen weiteren Parameter $k$ neben der Größe der Eingabe $n$. Dieser Parameter soll weitere Information über dasrnProblem zu Verfügung stellen und überdies eine typische Charakteristik beschreiben. Die Standard- Parameterisierung sieht $k$ als eine oberern(beziehungsweise untere) Schrankev für die Größe der Lösung im Fall eines Minimierungsproblems (beziehungsweise Maximierungsproblems). Eine parameterisierter Algorithmusrnsollte dann in der Lage sein das Problem in einer Laufzeit $f(k)\cdot n^\beta$ zu l\"osen, wobei $\beta$ eine Konstante und $f$ unabhängig von $n$rnist. Prinzipiell versucht diese Methode die kombinatorische Komplexität bezüglich des Parameters $k$ zu messen, falls dies überhaupt möglichrnist. Grundannahme hierbei ist, dass $k$ relativ klein ist verglichen mit der kompletten Eingabegrösse.rnIn beiden Gebieten ist der Entwurf von Verzweigungs-Algorithmen eine Standard- Technik. Diese Algorithmen lösen das Problem indem sie auf einernausgeklügelte Art und Weise den Lösungsraum traversieren. Schrittweise wählen sie ein Objekt aus der Eingabe aus und schaffen zwei neuernTeilprobleme, eines in dem das Objekt der zukünftigen Lösung zugesprochen wird, und ein weiteres in dem es aus dieser Lösung ausgeschlossenrnwird. In beiden Fällen kann es sein, dass durch die Fixierung dieses einen Objekts weitere ebenfalls fixiert werden. Ist dies der Fall dann istrndie Anzahl der besuchten möglichen Löungen kleiner als der gesamte Lösungsraum. Diese besuchten Lösungen können als Suchbaum betrachtetrnwerden. Um die Laufzeit solcher Algorithmen zu bestimmen benötigt man eine Methode die scharfe obere Schranken bezüglich der Suchbaumgrössernbereitstellt. Zu diesem Zweck wurde im Bereich der Exponentialzeit-Algorithmen eine mächtige Methode entwickelte, die sich Measure&Conquerrnnennt. Sie wurde bereits erfolgreich auf viele Probleme angewandt, insbesondere auf Probleme wo andere Versuche fehlschlugen die trivialernLaufzeitschranke zu unterbieten.rnIm Gegensatz dazu ist Measure&Conquer im Bereich der parameterisierten Algorithmen kaum bekannt. Diese Arbeit wird verschiedene Beispielernpräsentieren, wo diese Methode in diesem Bereich angewandt werden kann. Darüber hinaus werden Exponentialzeit-Algorithmen für harte Problemernvorgestellt, die Measure\&Conquer anwenden. Ein weitere Aspekt ist, dass eine Formalisierung (und Generalisierung) des Begriffes Suchbaum gegeben wird. Es wirdrngezeigt, dass für bestimmte Probleme diese Formalisierung sehr nützlich ist.

$Rev: 13581$