The authors defined
approximation algorithm as an
algorithm
that returns near optimal results. An
algorithm
for a problem is said to have an approximation ratio of $ \rho (n) $, if for any input size $n$, the cost $C$ of the solution produced by the
algorithm
is within a factor of $ \rho (n) $ of the cost $C*$ of an optimal solution : $ max \left( \frac{C}{C*},\frac{C*}{C} \right) \le \rho(n) $.
An
approximation scheme for an optimization problem is an approximation
algorithm
that takes as input not only an instance of the problem, but a value $ \sigma > 0 $ such that for any fixed $ \sigma $, the scheme is a $ (1 + \sigma) $ approximation
algorithm
. An approximation scheme is a
polynomial time approximation scheme if for any fixed $ \sigma > 0 $, the scheme runs in time polynomial in the size $n$ of its input instance and is a fully polynomial time approximation scheme if its running time is polynomial both in $ \frac{1}{\sigma} $ and in the size $n$ of the input instance.
The authors then provide an approximation
algorithm
for vertex cover problem and prove that it is a polynomial time 2-
approximation algorithm
.
The authors then provide an approximate
algorithm
for traveling salesman problem with triangle inequality. The authors also prove a theorem that good approximate tours cannot be found in polynomial time unless P = NP.
The authors then provide
greedy approximation algorithm for set cover problem and prove that it is a polynomial time $ \roh(n) $ - approximation
algorithm
.
The author then discuss two techniques for designing
approximation algorithms
:
- Randomization
- Linear Programming
The authors then provide a randomized approximation algorithm for MAX-3 CNF satisfiability. The author then provides an approximation algorithm for minimum weight vertex cover.
The authors then provide an exponential time exact algorithm for subset-sum-problem.
The authors then provide an algorithm to TRIM a list. Then the author provides an approximation algorithm for subset-sum-problem and prove that it is a fully polynomial time approximate scheme for the subset-sum-problem.
No comments:
Post a Comment