From worst-case to average-case efficiency [Elektronische Ressource] : approximating combinatorial optimization problems / vorgelegt von Kai Plociennik

Sujets

• Wissenschaft

Informations

• Publié par: technische_universitat_chemnitz
• Publié le: 01 janvier 2011
• Nombre de lectures: 7
• Langue: English

Extrait

From Worst-Case to Average-Case Eciency –
Approximating Combinatorial Optimization
Problems
von der Fakultät für Informatik
der Technischen Universität Chemnitz
genehmigte Dissertation
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften (Dr. rer. nat.)
vorgelegt von
Dipl.-Inf. Kai Plociennik
geboren am 13. Juni 1975 in Recklinghausen
Tag der Einreichung: 3. August 2010
Tag der Verteidigung: 27. Januar 2011
Gutachter: Prof. Dr. Hanno Lefmann,
Technische Universität Chemnitz
Prof. Dr. Andreas Goerdt,
Technische Universität ChemnitzAbstract
For many important combinatorial optimization problems, inapproximability
results exist, stating that under reasonable complexity-theoretic assumptions such as
P , NP, no worst-case ecient algorithm exists that achieves a certain (good)
approximation guarantee. This is an unfortunate situation, since in practical
applications, one often has to find a (good) solution for such a problem, and resources
like the available time are limited. It turns out, however, that many problems with
such inapproximability results can be solved satisfactorily in practice, i.e., there are
algorithms which typically find in relatively short time a relatively good solution.
Hence, there is a discrepancy between worst-case results and empirical
observations.
The reason for this discrepancy is that often, worst-case instances for an
algorithm are somehow artificial and do not typically appear in practice. Then, the
algorithm can typically perform much better than what its worst-case guarantees
promise. The worst-case view is too pessimistic here to adequately assess the
algorithm’s performance in practice. In average-case analysis of algorithms, one draws
a random input from the set of all inputs of a given size, e.g., the set of all graphs
with the same number of vertices, and then examines the expected algorithm
behavior for the random input. If one can prove that the expected behavior is much better
than the worst-case behavior, this can explain why the algorithm typically behaves
much better than in the worst case, and why a problem is tractable in practice even
though inapproximability results for it exist.
In this thesis, we consider three classical combinatorial optimization problems,
namely Independent Set, Coloring, and Shortest Common Superstring. For all
three problems, inapproximability results as mentioned above exist. Hence, one
knows lower bounds for the approximation guarantees which are achievable by
worst-case ecient algorithms (under reasonable assumptions). We show that the
w view in the inapproximability results is too pessimistic: We present
approximation algorithms whose approximation guarantees beat the lower bounds
for the ones we can achieve with worst-case ecient algorithms, and we perform
average-case analyses, showing that the expected running times of the algorithms
for random inputs from certain models are polynomial. Our algorithms are not
worst-case but at least average-case ecient. We also perform average-case
analyses for simple greedy algorithms for our problems, which are guaranteed to run
in polynomial time. We show that on the average and also with high probability,
these greedy algorithms perform much better than what their worst-case
guarantees promise with respect to the quality of the computed solutions. For example,
for Shortest Common Superstring, we are able to prove that the greedy algorithm
computes with probability exponentially close to 1 an almost optimal solution.
Furthermore, we investigate the behavior of some properties of random inputs for ourproblems. For example, we determine a tail bound on the optimal compression
that is achievable for a set of random strings for Shortest Common Superstring.
To sum up, we get algorithmic results on the typical behavior of algorithms for
random inputs, and structural results on the typical properties of the random inputs
themselves.
It can be argued that average-case analyses as above have a drawback: In some
applications, totally random inputs do not appropriately model inputs occurring in
practice. In many totally random input models, the random inputs with high
probability have properties that may not be present in real-world ones, and vice versa. To
provide a framework for reasonably modeling real-world inputs and analyzing the
behavior of algorithms for such inputs, Daniel A. Spielman and Shang-Hua Teng
introduced the smoothed analysis of algorithms. Here, a malicious adversary, who
tries to make the algorithm to be analyzed perform poorly, chooses an arbitrary
input for the considered problem. Then, the adversarial input is subject to a slight
random perturbation. Given an adversarial input, one determines the expected
algorithm behavior with respect to the random perturbation, and then one determines
the worst expected behavior over all possible adversarial choices. If one succeeds in
proving that even the worst expected behavior is still “good,” this can explain why
in practice, the algorithm performs well: Often, real-world inputs contain a small
amount of randomness, e.g., if the input comes from measurements performed on
a physical system. Then, the semi-random perturbation model of random inputs in
smoothed analysis reasonably models the inputs occurring in practice. The proof
that even a small amount of random noise leads to a good expected behavior,
regardless of the adversary’s choice, can then explain the good observed behavior of
the algorithm in practice.
In this thesis, we perform probabilistic analyses in the spirit of smoothed
analysis. We consider the problems Independent Set and Shortest Common
Superstring for perturbation models of random inputs, and achieve similar results as in
our average-case analyses.Contents
1 Introduction 1
1.1 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Smoothed Analysis and Semi-Random Inputs . . . . . . . 5
1.1.2 Expected Running Time and Average-Case Eciency . . 10
1.1.3 Approximation Algorithms . . . . . . . . . . . . . . . . . 16
1.1.4 Complexity Classes . . . . . . . . . . . . . . . . . . . . . 17
1.2 Results for Independent Set and Coloring . . . . . . . . . . . . . 18
1.2.1 Approximating Independent Set and Coloring for Random
Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . 20
1.2.2 Independent Set in Semi-Random Graphs 27
1.2.3 Previous and Related Work . . . . . . . . . . . . . . . . . 31
1.3 Results for Shortest Common Superstring . . . . . . . . . . . . . 32
1.3.1 Random Input Models and Previous Results . . . . . . . . 36
1.3.2 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.3.3 Further Notes on Previous and Related Work . . . . . . . 44
1.4 Summary of Our Results . . . . . . . . . . . . . . . . . . . . . . 45
1.5 Bibliographical Notes . . . . . . . . . . . . . . . . . . . . . . . . 47
2 Independent Set and Coloring for Random Hypergraphs 49
2.1 Greedy Coloring of Random Hypergraphs . . . . . . . . . . . . . 49
2.2 Approximating the Independence Number . . . . . . . . . . . . . 53
2.3 the Chromatic Number . . . . . . . . . . . . . . . 61
2.4 The Expected Behavior of Greedy Independent Set and Coloring . 64
2.5 Small Edge Probabilities . . . . . . . . . . . . . . . . . . . . . . 68
2.6 Completing the Proof of Lemma 2 . . . . . . . . . . . . . . . . . 73
2.7 Conclusions and Open Problems . . . . . . . . . . . . . . . . . . 75
3 Independent Set for Semi-Random Graphs 79
3.1 Greedy Coloring of Perturbed . . . . . . . . . . . . . . . 80
3.2 Upper Bounding the Independence Number . . . . . . . . . . . . 83
3.2.1 The Expectation of the Largest Eigenvalue . . . . . . . . 84
3.2.2 A Tail Bound on the Largest Eigenvalue . . . . . . . . . . 90
3.3 Approximating the Independence Number . . . . . . . . . . . . . 93
3.4 The Expected Behavior of Greedy Independent Set . . . . . . . . 97
3.5 Small Flip Probabilities . . . . . . . . . . . . . . . . . . . . . . . 99
3.6 Conclusions and Open Problems . . . . . . . . . . . . . . . . . . 101ii Contents
4 Shortest Common Superstring 103
4.1 Results in the Bernoulli and Perturbation Model . . . . . . . . . . 103
4.1.1 Upper Bounding the Optimal Compression . . . . . . . . 104
4.1.2 Computing a Shortest Superstring . . . . . . . . . . . . . 111
4.1.3 The Probabilistic PTAS . . . . . . . . . . . . . . . . . . . 114
4.2 Generalization to the Mixing Model . . . . . . . . . . . . . . . . 117
4.3 Conclusions and Open Problems . . . . . . . . . . . . . . . . . . 123
A Mathematical Definitions and Facts 125
A.1 Basic Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . 125
A.2 Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
A.2.1 The Independence Number and Largest Eigenvalue of
Random Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 128
A.2.2 The Trace of Even Powers of Symmetric Matrices . . . . 129
Bibliography 131
Index 138Chapter 1
Introduction
Contents
1.1 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Smoothed Analysis and Semi-Random Inputs . . . . . . . . 5
1.1.2 Expected Running Time and Average-Case Eciency . . . 10
1.1.3 Approximation Algorithms . . . . . . . . . . . . . . . . . . 16
1.1.4 Complexity Classes . . . . . . . . . . . . . . .