Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. An example of an approximation algorithm with a multiplicative guarantee is the Christofides-Serdyukov algorithm for the Travelling salesman problem. It provides a travelling salesman tour in a metric of length at most 3/2 times that of a shortest such tour.…

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. An example of an approximation algorithm with a multiplicative guarantee is the Christofides-Serdyukov algorithm for the Travelling salesman problem. It provides a travelling salesman tour in a metric of length at most 3/2 times that of a shortest such tour. A classic example of approximation algorithm providing an additive guarantee is the constructive proof of Vizing’s theorem. It shows how to color the edges of an undirected graph with at most \Delta + 1 colors, where \Delta is the maximum degree of any node. Since every edge incident on a maximum-degree node must have a different color, the constructive proof of the theorem gives a polynomial-time algorithm that uses at most one additional color than the minimum needed. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines. The design and analysis of approximation algorithms crucially involves a mathematical proof certifying the quality of the returned solutions in the worst case. This distinguishes them from heuristics such as annealing or genetic algorithms, which find reasonably good solutions on some inputs, but provide no clear indication at the outset on when they may succeed or fail. There is widespread interest in theoretical computer science to better understand the limits to which we can approximate certain famous optimization problems. For example, one of the long-standing open questions in computer science is to determine whether there is an algorithm that outperforms the 2-approximation for the Steiner Forest problem by Agrawal et al. The desire to understand hard optimization problems from the perspective of approximability is motivated by the discovery of surprising mathematical connections and broadly applicable techniques to design algorithms for hard optimization problems. One well-known example of the former is the Goemans–Williamson algorithm for maximum cut, which solves a graph theoretic problem using a semidefinite program coming from the first level of the sum of squares hierarchy. NP-hard problems vary greatly in their approximability; some, such as the knapsack problem, can be approximated within a multiplicative factor 1 + \epsilon , for any fixed \epsilon > 0 , and therefore produce solutions arbitrarily close to the optimum (such a family of approximation algorithms is called a polynomial-time approximation scheme or PTAS). Others are impossible to approximate within any constant, or even polynomial, factor unless P = NP, as in the case of the maximum clique problem. Therefore, an important benefit of studying approximation algorithms is a fine-grained classification of the difficulty of various NP-hard problems beyond the one afforded by the theory of NP-completeness. In other words, although NP-complete problems may be equivalent (under polynomial-time reductions) to each other from the perspective of exact solutions, the corresponding optimization problems behave very differently from the perspective of approximate solutions. ==Algorithm design techniques== By now there are several established techniques to design approximation algorithms. These include the following ones. Greedy algorithm Local search Enumeration and dynamic programming (which is also often used for parameterized approximations) Mathematical programming techniques. This involves modeling the considered problem with an appropriate mathematical programming formulation (typically a convex programming) such as Linear programming, Semidefinite programming, etc, to obtain a relaxation of solutions for the problem. Then further algorithmic techniques for these formulations are applied. Rounding-based methods. This involves solving the considered formulation for a good fractional solution and then converting it into an integer solution. Typical rounding techniques include simple threshold rounding, Randomized rounding, Iterative rounding, etc. Dual-fitting methods. This involves interpreting an intended combinatorial-based algorithm (typically a greedy one) as the process of computing a feasible solution for the dual program of the considered formulation. Primal-dual methods. Embedding the problem in some metric and then solving the problem on the metric. This is also known as metric embedding. Random sampling and the use of randomness in general in conjunction with the methods above. Approximation algorithms as a research area is closely related to and informed by inapproximability theory where the non-existence of efficient algorithms with certain approximation ratios is proved (conditioned on widely believed hypotheses such as the P ≠ NP conjecture) by means of reductions. In the case of the metric traveling salesman problem, the best known inapproximability result rules out algorithms with an approximation ratio less than 123/122 ≈ 1.008196 unless P = NP, Karpinski, Lampis, Schmied. Coupled with the knowledge of the existence of Christofides' 1.5 approximation algorithm, this tells us that the threshold of approximability for metric traveling salesman (if it exists) is somewhere between 123/122 and 1.5. While inapproximability results have been proved since the 1970s, such results were obtained by ad hoc means and no systematic understanding was available at the time. It is only since the 1990 result of Feige, Goldwasser, Lovász, Safra and Szegedy on the inapproximability of Independent Set and the famous PCP theorem, that modern tools for proving inapproximability results were uncovered. The PCP theorem, for example, shows that Johnson's 1974 approximation algorithms for Max SAT, set cover, independent set and coloring all achieve the optimal approximation ratio, assuming P ≠ NP. \forall i \in I, S(i) = {s \in S: i\Pi_s} finding the best solution s^* for a maximization or a minimization problem: s^* \in S(i) , c(s^*) = min/max \ c(S(i)) Given a feasible solution s \in S(i) , with s \neq s^* , we would want a guarantee of the quality of the solution, which is a performance to be guaranteed (approximation factor). Specifically, having A_{\Pi}(i) \in S_i , the algorithm has an approximation factor (or approximation ratio) of \rho(n) if \forall i \in I \ s.t. |i| = n , we have: for a minimization problem: \frac{c(A_{\Pi}(i))}{c(s^*(i))}\leq\rho(n) , which in turn means the solution taken by the algorithm divided by the optimal solution achieves a ratio of \rho(n) ; for a maximization problem: \frac{c(s^*(i))}{c(A_{\Pi}(i))}\leq\rho(n) , which in turn means the optimal solution divided by the solution taken by the algorithm achieves a ratio of \rho(n) ; The approximation can be proven tight (tight approximation) by demonstrating that there exist instances where the algorithm performs at the approximation limit, indicating the tightness of the bound. In this case, it's enough to construct an input instance designed to force the algorithm into a worst-case scenario. R(x,y) = \max \left ( \frac{OPT}{f(y)}, \frac{f(y)}{OPT} \right ), where f(y) is the value/cost of the solution y for the instance x. Clearly, the performance guarantee is greater than or equal to 1 and equal to 1 if and only if y is an optimal solution. If an algorithm A guarantees to return solutions with a performance guarantee of at most r(n), then A is said to be an r(n)-approximation algorithm and has an approximation ratio of r(n). Likewise, a problem with an r(n)-approximation algorithm is said to be r(n)-approximable or have an approximation ratio of r(n). For minimization problems, the two different guarantees provide the same result and that for maximization problems, a relative performance guarantee of ρ is equivalent to a performance guarantee of r = \rho^{-1} . In the literature, both definitions are common but it is clear which definition is used since, for maximization problems, as ρ ≤ 1 while r ≥ 1. The absolute performance guarantee \Rho_A of some approximation algorithm A, where x refers to an instance of a problem, and where R_A(x) is the performance guarantee of A on x (i.e. ρ for problem instance x) is: \Rho_A = \inf \{ r \geq 1 \mid R_A(x) \leq r, \forall x \}. That is to say that \Rho_A is the largest bound on the approximation ratio, r, that one sees over all possible instances of the problem. Likewise, the asymptotic performance ratio R_A^\infty is: R_A^\infty = \inf \{ r \geq 1 \mid \exists n \in \mathbb{Z}^+, R_A(x) \leq r, \forall x, |x| \geq n\}. That is to say that it is the same as the absolute performance ratio, with a lower bound n on the size of problem instances. These two types of ratios are used because there exist algorithms where the difference between these two is significant. In the literature, an approximation ratio for a maximization (minimization) problem of c - ϵ (min: c + ϵ) means that the algorithm has an approximation ratio of c ∓ ϵ for arbitrary ϵ > 0 but that the ratio has not (or cannot) be shown for ϵ = 0. An example of this is the optimal inapproximability — inexistence of approximation — ratio of 7 / 8 + ϵ for satisfiable MAX-3SAT instances due to Johan Håstad. As mentioned previously, when c = 1, the problem is said to have a polynomial-time approximation scheme. An ϵ-term may appear when an approximation algorithm introduces a multiplicative error and a constant error while the minimum optimum of instances of size n goes to infinity as n does. In this case, the approximation ratio is c ∓ k / OPT = c ∓ o(1) for some constants c and k. Given arbitrary ϵ > 0, one can choose a large enough N such that the term k / OPT 0. ==Citations== ==References== Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Chapter 35: Approximation Algorithms, pp. 1022–1056. Dorit S. Hochbaum, ed. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. . Chapter 9: Various Notions of Approximations: Good, Better, Best, and More ==External links== Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1357586553 under CC BY-SA 4.0; modifications have been made.