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. 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

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.

NP-hard problems vary greatly in their approximability; some, such as the knapsack problem, can be approximated within a multiplicative factor nO(1/ϵ) for a ϵ>0.

Given an optimization problem:

I the set of inputs and ∀i∈I,S(i)=s∈S:iΠs

finding the best solution c(s∗)=min/max c(S(i))

Given a feasible solution AΠ(i)∈Si, the algorithm has an approximation factor (or approximation ratio) of c(AΠ(i))c(s∗(i))≤ρ(n), which in turn means the solution taken by the algorithm divided by the optimal solution achieves a ratio of ρ(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.

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.

1; \\\\ \\rho \\mathrm{OPT} \\leq f(x) \\leq \\mathrm{OPT},\\qquad\\mbox{if } \\rho < 1.\\end{cases}"}}'>{OPT≤f(x)≤ρOPT,if ρ>1;ρOPT≤f(x)≤OPT,if ρ<1.

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

r=ρ−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 PA=inf⁡{r≥1∣RA(x)≤r,∀x}.

That is to say that RA∞=inf⁡{r≥1∣∃n∈ℤ+,RA(x)≤r,∀x,|x|≥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.

Performance guarantees

	r-approx	ρ-approx	rel. error	rel. error	norm. rel. error	abs. error
max: ρOPT	(1−c)OPT+cWORST	rOPT	(1−c)−1OPT	1 2 Bernard., Shmoys, David (2011). The design of approximation algorithms. Cambridge University Press. ISBN 9780521195270. OCLC 671709856.{{cite book}}: CS1 maint: multiple names: authors list (link) ↑ Karpinski, Marek; Lampis, Michael; Schmied, Richard (2015-12-01). "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. ↑ Johnson, David S. (1974-12-01). "Approximation algorithms for combinatorial problems". Journal of Computer and System Sciences. 9 (3): 256–278. doi:10.1016/S0022-0000(74)80044-9. ↑ G. Ausiello; P. Crescenzi; G. Gambosi; V. Kann; A. Marchetti-Spaccamela; M. Protasi (1999). Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. 1 2 3 4 5 Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 978-3-540-65367-7. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. Williamson, David P.; Shmoys, David B. (April 26, 2011), The Design of Approximation Algorithms, Cambridge University Press, ISBN 978-0521195270 External links edit Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems. Optimization: Algorithms, methods, and heuristics
Unconstrained nonlinear Functions Golden-section search Powell's method Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method		Optimization computes maxima and minima.
Constrained nonlinear General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming
Convex optimization Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke Active-set method
Combinatorial Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow
Metaheuristics Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search
Software

• GND

• Approximation algorithms</span>"}]]}'>United States
• Algorithmes d'approximation</span>"}]]}'>France
• Algorithmes d'approximation</span>"}]]}'>BnF data
• Israel

• Yale LUX