Approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to NPhard optimization problems with provable guarantees on the distance of the returned solution to the optimal one.^{[1]} 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. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos^{[2]} 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.^{[1]} 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 longstanding open questions in computer science is to determine whether there is an algorithm that outperforms the 1.5 approximation algorithm of Christofides to the Metric Traveling Salesman Problem. 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 wellknown example of the former is the GoemansWilliamson algorithm for Maximum Cut which solves a graph theoretic problem using high dimensional geometry.^{[3]}
Contents
Introduction
A simple example of an approximation algorithm is one for the Minimum Vertex Cover problem, where the goal is to choose the smallest set of vertices such that every edge in the input graph contains at least one chosen vertex. One way to find a vertex cover is to repeat the following process: find an uncovered edge, add both its endpoints to the cover, and remove all edges incident to either vertex from the graph. As any vertex cover of the input graph must use a distinct vertex to cover each edge that was considered in the process (since it forms a matching), the vertex cover produced, therefore, is at most twice as large as the optimal one. In other words, this is a constant factor approximation algorithm with an approximation factor of 2. Under the recent Unique Games Conjecture, this factor is even the best possible one.^{[4]}
NPhard problems vary greatly in their approximability; some, such as the Knapsack Problem, can be approximated within a multiplicative factor , for any fixed , 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 finegrained classification of the difficulty of various NPhard problems beyond the one afforded by the theory of NPcompleteness. In other words, although NPcomplete 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
 Solving a convex programming relaxation to get a fractional solution. Then converting this fractional solution into a feasible solution by some appropriate rounding. The popular relaxations include the following.
 Linear programming relaxations
 Semidefinite programming relaxations
 PrimalDual Methods
 Dual Fitting
 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.
A Posteriori Guarantees
While approximation algorithms always provide an a priori worst case guarantee (be it additive or multiplicative), in some cases they also provide an a posteriori guarantee that is often much better. This is often the case for algorithms that work by solving a convex relaxation of the optimization problem on the given input. For example, there is a different approximation algorithm for Minimum Vertex Cover that solves a linear programming relaxation to find a vertex cover that is at most twice the value of the relaxation. Since the value of the relaxation is never larger than the size of the optimal vertex cover, this yields another 2approximation algorithm. While this is similar to the a priori guarantee of the previous approximation algorithm, the guarantee of the latter can be much better (indeed when the value of the LP relaxation is far from the size of the optimal vertex cover).
Hardness of Approximation
Approximation algorithms as a research area is closely related to and informed by inapproximability theory where the nonexistence 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.^{[5]} 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 adhoc 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^{[6]} and the famous PCP theorem,^{[7]} 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.^{[8]}
Practicality
Not all approximation algorithms are suitable for direct practical applications. Some involve solving nontrivial linear programming/semidefinite relaxations (which may themselves invoke the ellipsoid algorithm), complex data structures, or sophisticated algorithmic techniques, leading to difficult implementation issues or improved running time performance (over exact algorithms) only on impractically large inputs. Implementation and running time issues aside, the guarantees provided by approximation algorithms may themselves not be strong enough to justify their consideration in practice. Despite their inability to be used "out of the box" in practical applications, the ideas and insights behind the design of such algorithms can often be incorporated in other ways in practical algorithms. In this way, the study of even very expensive algorithms is not a completely theoretical pursuit as they can yield valuable insights.
In other cases, even if the initial results are of purely theoretical interest, over time, with an improved understanding, the algorithms may be refined to become more practical. One such example is the initial PTAS for Euclidean TSP by Sanjeev Arora (and independently by Joseph Mitchell) which had a prohibitive running time of for a approximation.^{[9]} Yet, within a year these ideas were incorporated into a nearlinear time algorithm for any constant .^{[10]}
Performance guarantees
For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a ρapproximation algorithm A is defined to be an algorithm for which it has been proven that the value/cost, f(x), of the approximate solution A(x) to an instance x will not be more (or less, depending on the situation) than a factor ρ times the value, OPT, of an optimum solution.
The factor ρ is called the relative performance guarantee. An approximation algorithm has an absolute performance guarantee or bounded error c, if it has been proven for every instance x that
Similarly, the performance guarantee, R(x,y), of a solution y to an instance x is defined as
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).^{[11]}^{[12]}
One may note that 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 . 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 of some approximation algorithm A, where x refers to an instance of a problem, and where is the performance guarantee of A on x (i.e. ρ for problem instance x) is:
That is to say that is the largest bound on the approximation ratio, r, that one sees over all possible instances of the problem. Likewise, the asymptotic performance ratio is:
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.
rapprox^{[11]}^{[12]}  ρapprox  rel. error^{[12]}  rel. error^{[11]}  norm. rel. error^{[11]}^{[12]}  abs. error^{[11]}^{[12]}  

max:  
min: 
Epsilon terms
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 MAX3SAT instances due to Johan Håstad.^{[13]} As mentioned previously, when c = 1, the problem is said to have a polynomialtime 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 < ϵ for every n ≥ N. For every fixed ϵ, instances of size n < N can be solved by brute force , thereby showing an approximation ratio — existence of approximation algorithms with a guarantee — of c ∓ ϵ for every ϵ > 0.
See also
 Domination analysis considers guarantees in terms of the rank of the computed solution.
 PTAS  a type of approximation algorithm that takes the approximation ratio as a parameter
 APX is the class of problems with some constantfactor approximation algorithm
 Approximationpreserving reduction
 Exact algorithm
Citations
This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (April 2009) (Learn how and when to remove this template message)

 ^ ^{a} ^{b} Bernard., Shmoys, David (2011). The design of approximation algorithms. Cambridge University Press. ISBN 9780521195270. OCLC 671709856.
 ^ Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (19900101). "Approximation algorithms for scheduling unrelated parallel machines". Mathematical Programming. 46 (1–3): 259–271. doi:10.1007/BF01585745. ISSN 00255610.
 ^ Goemans, Michel X.; Williamson, David P. (November 1995). "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming". J. ACM. 42 (6): 1115–1145. doi:10.1145/227683.227684. ISSN 00045411.
 ^ Khot, Subhash; Regev, Oded (20080501). "Vertex cover might be hard to approximate to within 2−ε". Journal of Computer and System Sciences. Computational Complexity 2003. 74 (3): 335–349. doi:10.1016/j.jcss.2007.06.019.
 ^ Karpinski, Marek; Lampis, Michael; Schmied, Richard (20151201). "New inapproximability bounds for TSP". Journal of Computer and System Sciences. 81 (8): 1665–1677. arXiv:1303.6437. doi:10.1016/j.jcss.2015.06.003.
 ^ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (March 1996). "Interactive Proofs and the Hardness of Approximating Cliques". J. ACM. 43 (2): 268–292. doi:10.1145/226643.226652. ISSN 00045411.
 ^ Arora, Sanjeev; Safra, Shmuel (January 1998). "Probabilistic Checking of Proofs: A New Characterization of NP". J. ACM. 45 (1): 70–122. doi:10.1145/273865.273901. ISSN 00045411.
 ^ Johnson, David S. (19741201). "Approximation algorithms for combinatorial problems". Journal of Computer and System Sciences. 9 (3): 256–278. doi:10.1016/S00220000(74)800449.
 ^ Arora, S. (October 1996). "Polynomial time approximation schemes for Euclidean TSP and other geometric problems". Proceedings of 37th Conference on Foundations of Computer Science: 2–11. doi:10.1109/SFCS.1996.548458.
 ^ Arora, S. (October 1997). "Nearly linear time approximation schemes for Euclidean TSP and other geometric problems". Proceedings 38th Annual Symposium on Foundations of Computer Science: 554–563. doi:10.1109/SFCS.1997.646145.
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} G. Ausiello; P. Crescenzi; G. Gambosi; V. Kann; A. MarchettiSpaccamela; M. Protasi (1999). Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties.
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} Viggo Kann (1992). On the Approximability of NPcomplete Optimization Problems (PDF).
 ^ Johan Håstad (1999). "Some Optimal Inapproximability Results". Journal of the ACM. doi:10.1145/502090.502098.
References
 Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3540653678.
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGrawHill, 2001. ISBN 0262032937. Chapter 35: Approximation Algorithms, pp. 1022–1056.
 Dorit S. Hochbaum, ed. Approximation Algorithms for NPHard problems, PWS Publishing Company, 1997. ISBN 0534949681. Chapter 9: Various Notions of Approximations: Good, Better, Best, and More
 Williamson, David P.; Shmoys, David B. (April 26, 2011), The Design of Approximation Algorithms, Cambridge University Press, ISBN 9780521195270
External links
 Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems.