«Algorithmic Approaches for Solving Hard Problems: Approximation and Complexity A dissertation submitted to the Swiss Federal Institute of Technology ...»
Diss. ETH No. 18748
Algorithmic Approaches for Solving Hard Problems:
Approximation and Complexity
A dissertation submitted to the
Swiss Federal Institute of Technology Zurich (ETH)
for the degree of
Doctor of Sciences
Dipl.-Inform. Rheinisch-Westf¨lische Technische Hochschule Aachen
Born on September 24, 1979
citizen of Germany
accepted on the recommendation of
Prof. Dr. J. Hromkoviˇ, examiner
Prof. Dr. P. Widmayer, co-examiner Prof. Dr. P. Rossmanith, co-examiner iii Zusammenfassung In dieser Dissertation behandeln wir Methoden zum L¨sen schwerer Probleme, die uber die o ¨ klassische Approximation hinausgehen. Diese Methoden sind aus zwei Gr¨nden n¨tzlich. Zum u u einen bieten sie neue M¨glichkeiten, L¨sungen zu algorithmischen Problemen zu ﬁnden. Zum o o anderen bilden sie die Grundlage f¨r neue Techniken zur Analyse der Frage, welche Faktoren u ein Problem NP-schwer machen bzw. weshalb Probleme schwer zu approximieren sind. Im gleichen Kontext schließen wir diese Dissertation mit komplexit¨tstheoretischen Resultaten a ab.
Unser erstes Resultat besch¨ftigt sich mit der Struktur von Eingabeinstanzen f¨r das a u Traveling-Salesman-Problem in metrischen Graphen. Das Ziel hierbei ist es, einen Kreis mit minimalen Kosten zu ﬁnden, der jeden Knoten des Graphen genau ein Mal besucht. Der Christoﬁdes-Algorithmus, der schon im Jahr 1976 ver¨ﬀentlicht wurde, ist 1.5-approximativ o und damit der bislang beste Approximationsalgorithmus f¨r dieses Problem. F¨r unsere u u Analyse betrachten wir zudem den bislang besten Algorithmus f¨r ein verwandtes Problem, u das Hamilton-Pfad-Problem in metrischen Graphen mit vorgegebenen Endknoten. Dieser Algorithmus stammt von Hoogeveen und ist 5/3-approximativ. Wir charakterisieren schwere Eingaben
Abstract In this dissertation, we study approaches beyond classical approximation for solving hard problems. The use of these approaches is twofold. On the one hand, they establish new computational possibilities for ﬁnding solutions to hard problems. On the other hand, they provide techniques to analyze the reason why certain problems are NP -hard or hard to approximate.
Accordingly, the main focus of this thesis is the analysis of computational hardness, approximability, and parameters that inﬂuence the hardness of problems. In the same context, we conclude the thesis with complexity-theoretic results.
Our ﬁrst result concerns the structure of hard input instances for the traveling salesman problem in metric graphs. The goal of the problem is to ﬁnd a minimum cost cycle that contains each vertex of the graph exactly once. Christoﬁdes’ algorithm, which was ﬁrst published in 1976 and achieves an approximation ratio of 1.5, is to date the best approximation algorithm for this problem. For our analysis, we also consider the best up-to-date algorithm for a related problem, the Hamiltonian path problem with predeﬁned end vertices in metric graphs. This algorithm is due to Hoogeveen and achieves a 5/3-approximation. Here, we characterize hard input instances for Christoﬁdes’ algorithm and Hoogeveen’s algorithm by relating the two underlying problems. We show that the sets of metric worst-case instances for both algorithms are disjoint in the following sense: there is an algorithm that, for any input instance, either ﬁnds a Hamiltonian tour that is signiﬁcantly better than 1.5-approximative or a set of Hamiltonian paths between all pairs of endpoints, all of which are signiﬁcantly better than 5/3-approximative. In the context of approximation algorithms, we also present a new, improved algorithm for the traveling salesman problem, where some vertices have to be visited in a predeﬁned order.
We continue with considering reoptimization problems. There, we handle the question whether the knowledge of an optimal solution to the unaltered instance can help in solving a locally modiﬁed instance.
In terms of this idea, we analyze the approximability of the Steiner tree problem. We show that, even in very restricted cases, this problem remains APX -hard. On the one hand, we consider edge costs that are restricted to the values 1 and 1 + γ for an arbitrary small γ 0.
On the other hand, we provide the algorithm with additional information: the input consists of a Steiner tree instance together with an optimal solution, as well as a second Steiner tree instance, where one vertex is added. Now, the goal is to minimize the cost of a solution for the modiﬁed input. This way, our result discloses a sharp edge between eﬃcient solvability and inapproximability.
We present the ﬁrst NP -hardness proofs for the Steiner tree reoptimization problem.
In particular, we show that all Steiner tree reoptimization variants that were previously considered, namely, adding terminals or non-terminals, removing terminals or non-terminals, changing the cost of an edge, and changing the status of a vertex from terminal to nonterminal or vice versa, are NP-hard, even if the edge costs are restricted to the values 1 and 1 + γ for an arbitrary positive γ. For removing terminal or non-terminal vertices, we even show APX -hardness.
The algorithmic results for reoptimization vary considerably, depending on the problem and the type of local modiﬁcation. The transition from the triangle inequality to the sharpened β-triangle inequality can inﬂuence whether there is a PTAS for a problem (assuming vi that P = NP). To this end, we consider the more general class of graphs with a polylogarithmically bounded cost function, where each edge has a cost of at least 1. Then, for some of the Steiner tree reoptimization variants, we even obtain a PTAS. This class of graphs also contains all graphs with a cost function obeying the sharpened β-triangle inequality.
For the Steiner tree problem where the local modiﬁcation is to change the status of a vertex from terminal to non-terminal or vice versa, we present a 1.5-approximation algorithm, improving the best currently known approximation for the classical minimum Steiner tree problem, which is 1 + (ln 3)/2 ≈ 1.55. We also present results concerning the change of the edge costs as local modiﬁcation.
Furthermore, we present an analysis of hard instances for the 1.4-approximation algorithm for the traveling salesman reoptimization problem with increasing edge costs from  and give several parameters such that any change results in a better approximation ratio. We conclude the reoptimization results by considering the shortest common superstring reoptimization problem. Given a set of strings, the problem consists in ﬁnding a shortest superstring that contains each of the given strings as substring. We show that the local modiﬁcations of both adding a string and removing a string are NP-hard and we analyze lower bounds on the approximation ratio achievable by a quite natural and promising algorithm for that problem.
The remaining results are concerning complexity theory. All approaches mentioned above depended on the assumption that P = NP holds. For online problems, however, the main focus is on the quality that can be guaranteed at all. Also here, we approach the problem by using novel techniques. We investigate to what extent the solution quality can be improved in terms of advice complexity. We assume that an oracle provides the content of an advice tape. Now the question is, how many of the written bits of advice have to be accessed at most in order to achieve a certain solution quality. We focus on a variant of the job shop √ scheduling problem and show a lower bound of Ω( n) advice bits to be necessary for achieving optimality.
Finally, we handle size complexity of randomized automata. The problem of whether nondeterminism helps is not even answered in computational models as weak as two-way automata. Therefore, we investigate related questions on slightly weaker models. We show that, for any reasonable randomized model, the number of states of sweeping ﬁnite automata and rotating ﬁnite automata cannot diﬀer more than by a polynomial factor.
vii Acknowledgment I would like to acknowledge the great debt that I owe my advisor, Juraj Hromkoviˇ, who, c with his humble and honest way to deal with people and his extraordinary inspiration and ideas, helped me to develop my abilities as a researcher and, even more important, helped me to grow as a person. He was both a source of invaluable advice on research and of persistent motivation to discover the beauty of the mountains. Due to his infectious verve I discovered some of the most impressive summits of Switzerland.
The camaraderie in our research group was always very pleasant and enjoyable. This was mainly because of all my wonderful colleagues who enabled a constructive and friendly atmosphere. I would like to express my special gratitude to Hans-Joachim B¨ckenhauer, who o never got tired of listening to my ideas, provided constructive criticism of my research, and who made a great eﬀort to proofread this dissertation. Thanks are also due to Christos Kapoutsis, who inﬂuenced me to improve my writing skills and to sharpen my perception of details. I also thank Dennis Komm and Richard Kr´loviˇ for the hours of enlightening a c discussions.
In the early days of my graduate studies, I was given the opportunity to visit the King’s College in London. That stay helped me to have a successful start on my research. I would like to thank Kathleen Steinh¨fel wholeheartedly for her invitation and for her hospitality.
o I am also grateful to Ralf Klasing for inviting me to do ﬁve weeks of research in the Laboratoire Bordelais de Recherche en Informatique. I will never forget his extraordinary kindness. The fruitful discussions we had in Bordeaux helped me to develop some of the ideas that later on proved to be very important for this dissertation.
I would like to express my heartfelt gratitude to my mother and sister, who always supported me with their love and happiness.
Most of all, I would like to thank my wife Gaya. Meeting her was without doubt the most valuable coincidence of coming to Switzerland.
Introduction This dissertation focuses on new approaches to hard algorithmic problems. There are two main reasons for this: to provide new algorithmic techniques for ﬁnding good approximative solutions and to increase the understanding of the essence of the hardness involved.
More speciﬁcally, we ﬁrst investigate approximation and approximability of NP -hard optimization problems. It is to be expected that these problems do not admit any feasible algorithm that guarantees an exact solution within a reasonable time, since it is conjectured that P is not equal to NP. If this conjecture is correct, then there are no exact polynomialtime algorithms for these optimization problems. Thus, instead of trying to ﬁnd optimal solutions, we aim for good, but not necessarily optimal, solutions.
The research of approximation has led to impressive results. For some NP -hard optimization problems such as the knapsack problem, it is feasible to compute solutions that are very close to optimal ones, using a so called fully polynomial-time approximation scheme .
The importance of approximation, however, reaches far beyond its applications in operations research. The NP-hard optimization problems can be classiﬁed according to their approximability. This way, we obtain a much more detailed view on the hardness of these problems.
Some deep results in this area were achieved using a characterization of NP via so-called probabilistically checkable proofs [5, 42] which enabled new techniques for showing approximation hardness. Tight bounds on the approximability were shown by H˚ astad  for some problems such as MaxE3SAT, the problem to maximize the number of satisﬁed clauses in a boolean formula, where each clause has exactly three literals.
Despite these achievements, however, there are many important problems for which the known lower bounds on the approximability and the currently best achieved approximation rate diﬀer considerably. One of these problems is the metric traveling salesman problem.
Here, one is given a complete edge-weighted graph with metric cost function and one searches for a minimum-cost cycle that visits each vertex exactly once. A cost function is metric, if no edge between two vertices is more expensive than any path between them. The metric traveling salesman problem is well-known to be approximable within a constant factor of 1.5 due to Christoﬁdes’ algorithm . For the best lower bound, however, we only know that ﬁnding a better approximation ratio than 117/116 is NP -hard .
Due to the long time in which Christoﬁdes’ result remains unimproved, it seems worthwhile to have a close look at the properties of hard input instances for his algorithm. In order to do this, we extend the concept of win/win algorithms. The general idea of win/win algorithms is
2 CHAPTER 1. INTRODUCTIONthat we are given two related hard problems deﬁned on the same input instances. Now, we ask whether hard inputs for one problem are also hard for the other one. We tackle this question by searching for algorithms that are guaranteed to ﬁnd a good solution for at least one of the two problems. This research relates to win/win-strategies in parameterization which provide a popular method for designing parameterized algorithms , as well as to the design of hybrid algorithms as used by Vassilevska et al. . In this type of hybrid algorithms, for a single problem, one either ﬁnds a good solution eﬃciently or one is guaranteed to have an improved (exponential) runtime for computing an exact solution.
In contrast to previous approaches, we apply the win/win technique to approximation.
Given two diﬀerent problems with the same set of input instances, we want to guarantee at least one of the problems to be approximated with a better approximation ratio than the best one we can guarantee by using known algorithms. Besides the algorithmic meaning — we are guaranteed to have a good solution for one of the problems — we classify hard input instances for one algorithm according to the hardness for another algorithm, which is useful for a deeper understanding of why certain input instances are hard.