The Design of Approximation Algorithms
The Design of Approximation Algorithms
1 An introduction to approximation algorithms
Definition 1.1: An $\alpha$-approximation algorithm is …
Definition 1.2: A polynomial-time approximation scheme (PTAS) is …
Theorem 1.3: For any MAX SNP-hard problem, there does not exist a polynomial-time approximation scheme, unless $P = NP$.
An example: the maximum clique problem
2 Greedy algorithm and local search
2.1 Scheduling jobs with deadlines on a single machine
Assume that all due dates are negative, which implies that the optimal value is always positive. We shall give a 2-approximation algorithm for this special case.
2.2 The k-center problem
A greedy 2-approximation algorithm.
There is no $\alpha$-approximation algorithm for the k-center problem for $\alpha < 2$ unless $P = NP$.
2.3 Scheduling jobs on identical parallel machines
the local search algorithm and the greedy algorithm are 2-approximation.
the longest processing time rule is a 4/3-approximation algorithm.
2.4 The traveling salesman problem
the double-tree algorithm is a 2-approximation algorithm.
the Christofides’ algorithm is a 3/2-approximation algorithm.
2.5 Maximizing float in bank accounts
2.6 Finding minimum-degree spanning trees
The locally optimal tree: no move that can reduce the degree of any node having degree between $\Delta(T) - l$ and $\Delta(T)$.
Theorem 2.19: Let T be a locally optimal tree. Then $\Delta(T) \le 2OPT + l$, where $l = \lceil \log_2{n} \rceil$.
Theorem 2.20: The algorithm finds a locally optimal tree in polynomial time.