<p>One example is related to <a href="http://en.wikipedia.org/wiki/Tree_decomposition">tree decompositions</a> and graphs of small treewidth.</p>

<p>Typically, <em>if</em> we are given a tree decomposition, it is fairly straightforward to apply dynamic programming to solve a given graph problem $B$ optimally. The running time depends on the width of the tree decomposition.</p>

<p>However, usually we are not given a tree decomposition, but we need to find it. To solve problem $B$ as fast as possible, we would like to find a tree decomposition of the smallest possible width – now this is our problem $A$.</p>

<p>We could try to solve problem $A$ exactly, but then we might waste too much time in part $A$. One possible approach is to use an approximation algorithm for part $A$. Then part $A$ is faster, at a cost of worse running time guarantees in part $B$.</p>

<hr>

<p>Another example is related to compilers and <a href="http://en.wikipedia.org/wiki/Register_allocation">register allocation</a>. Assume that we have implemented an exact algorithm that solves a problem $B$ in polynomial time. The running time of the algorithm depends, in part, on how well the compiler managed to assign variables onto CPU registers – this is our problem $A$.</p>

<p>The solution of problem $B$ is correct even if the compiler uses an approximation algorithm to solve problem $A$; however, an approximation factor in problem $A$ affects the running time of algorithm $B$.</p>

CC BY-SA 3.0
2011-12-30T20:08:38.143Z
While the treewidth example works in principle, it would be hard to execute in practice because it is very hard to approximate treewidth at all well (since you can approximate clique)
Suresh Venkat
CC BY-SA 3.0
2011-12-30T12:53:39.237Z
2011-12-30T13:07:04.487Z
2011-12-30T13:07:04.487Z
Jukka Suomela
<p>An example of an approximation algorithm that converges to the exact solution would be the Ellipsoid algorithm for solving LPs - if the coefficients are rationals, then one can compute a minimum distance between two vertices of the feasible polytope. Now, the ellipsoid algorithm computes repeatedly a smaller and smaller elliposoid that must contain the optimal solution. Once the elliposoid is small enough to contain only such a single vertex, you essentially found the optimal vertex. This is why LP is weakly polynomial.</p>
<p>As for an example closer to your outline - consider Matousek's algorithm for finding the smallest disk containing <span class="math-container">$k$</span> points in the plane. The algorithm first finds a 2-approixmation (in the radius), break the plane into appropriate grid, and the solves the problem inside each grid cluster exactly, using a slow algorithm.</p>
<p>Finally, going further a field - many algorithm that follows the alteration technique (take a random sample - and then do some fixups to get what you want) falls into such a framework. One cute example is the algorithm for computing the median using random sampling (see the book by Motwani and Raghavan). There are many such examples - arguably many of the randomized incremental algorithms in Computational Geometry falls into this framework.</p>

CC BY-SA 4.0
2011-12-30T13:36:47.350Z
2020-08-12T20:42:39.427Z
2020-08-12T20:42:39.427Z
Sariel Har-Peled
<p>Many <b>output-sensitive</b> algorithms employ this technique. For example, here is a simple problem on which this technique can be used:</p>
<p><b>Problem</b>. You are given an array A[1..<i>n</i>] in which each element is atmost <i>k</i> positions away from the position it would have been in if A was sorted. 
<p>For example, A[1..7] shown below could be an input array for <i>k</i> = 2. <br><br>
<img src="https://i.sstatic.net/WrNjt.jpg">
</p>
<p>Design an algorithm to sort the array in O(<i>n</i> log <i>k</i>) time, assuming <i>k</i> is unknown.</p></p>
<p><i> Problem Source: <a href="https://www.algomuse.net" rel="nofollow noreferrer">Algo Muse</a> Archive.</i></p>

CC BY-SA 4.0
2011-12-31T17:50:05.567Z
2020-08-05T16:22:24.513Z
2020-08-05T16:22:24.513Z
Jagadish
<p>An example from the parameterized complexity is a <a href="http://en.wikipedia.org/wiki/Kernelization">kernelization</a> for the <a href="http://en.wikipedia.org/wiki/Vertex_cover">vertex cover problem</a> using a theorem of Nemhauser and Trotter.</p>

<p>In the minimum vertex cover problem, we are given an undirected graph G, and we need to find a vertex cover of G of minimum size.  A vertex cover of an undirected graph is a vertex subset that touches all edges.</p>

<p>Here is an exact algorithm that uses an approximation at the first phase.</p>

<p>Phase 1: Set up <a href="http://en.wikipedia.org/wiki/Vertex_cover#ILP_formulation">the integer linear programming formulation of the minimum vertex cover problem</a>.  It's known (or easy to show) that a basic optimal solution of the linear programming relaxation is half-integral (i.e., every coordinate is either 0, 1, or 1/2).  Such a basic optimal solution can be found by a usual polynomial-time algorithm for linear programming (or in this special case, we can formulate it as a network flow problem, so we can solve it combinatorially in polynomial time).  Having such a basic optimal solution, we round it up to obtain a feasible solution to the original integer linear programming problem.  Let S be the corresponding vertex subset.  It's good to note that S is a 2-approximation of the given minimum vertex cover instance.</p>

<p>Phase 2: Find a minimum vertex cover in the subgraph induced by S (for example by an exhaustive search).  A theorem by Nemhauser and Trotter states that this subgraph contains an optimal solution of the original input graph.  So, the correctness of this approach follows.</p>

<p>You may consult <a href="http://rads.stackoverflow.com/amzn/click/0198566077">a book by Niedermeier on fixed-parameter algorithms</a> for this algorithm.</p>

CC BY-SA 3.0
2011-12-30T14:45:19.007Z
2011-12-30T14:45:19.007Z
Yoshio Okamoto
<p>Approximation algorithms might give output up to some constant factor. This is a bit less satisfying than exact algorithms.</p>

<p>However, constant factors are ignored in time complexity.</p>

<p>So I wonder if the following trick is possible or was used, to solve some problem $B \circ A$:</p>

<ol>
<li>Use an approximation algorithm solving problem $A$ to get solution $S$ within constant factor;</li>
<li>Use an exact algorithm, solving problem $B$, whose runtime depends on weight of $S$ but works as long as $S$ is a correct solution.</li>
</ol>

<p>This way the approximation is a "subprocedure" of an exact algorithm, and the constant factor lost in step 1 is swallowed in step 2.</p>

CC BY-SA 3.0
2011-12-30T07:39:06.700Z
Crosspost from [math SE](http://math.stackexchange.com/questions/94099/)
sdcvvc
CC BY-SA 3.0
2011-12-30T08:09:41.290Z
Would you clarify what you mean by $B \circ A$ and the weight of $S$?
Yoshio Okamoto
CC BY-SA 3.0
2011-12-30T08:20:56.633Z
This is informal, for concreteness: $A,B$ are [search problems](http://en.wikipedia.org/wiki/Search_problem), $A$ is thought as an optimization problem (so the solutions carry some weight) and $B \circ A$ is composition of relations.
sdcvvc
CC BY-SA 3.0
2011-12-30T14:47:02.903Z
The answers would be a collection.  So, I would think it'd be more appropriate to make it community wiki.
Yoshio Okamoto
CC BY-SA 3.0
2011-12-30T16:32:28.803Z
Adding the big-list tag is enough, there is no need to make it community wiki IMHO.
Gopi
CC BY-SA 4.0
2020-08-05T16:58:54.467Z
Quote from Vijay Vazirani's book on approximation algorithm. "Although this may seem a paradox, all exact
science is dominated by the idea of approximation.
Bertrand Russell (1872–1970)"
Chandra Chekuri
<ds.algorithms><big-list><approximation-algorithms>
Approximation algorithms used in exact algorithms
sdcvvc
# Approximation algorithms used in exact algorithms

(Asked by: username_0 on 2011-12-30)

Approximation algorithms might give output up to some constant factor. This is a bit less satisfying than exact algorithms.

However, constant factors are ignored in time complexity.

So I wonder if the following trick is possible or was used, to solve some problem $B \circ A$:

1. Use an approximation algorithm solving problem $A$ to get solution $S$ within constant factor;
2. Use an exact algorithm, solving problem $B$, whose runtime depends on weight of $S$ but works as long as $S$ is a correct solution.

This way the approximation is a "subprocedure" of an exact algorithm, and the constant factor lost in step 1 is swallowed in step 2.

**Tags:** ds.algorithms, big-list, approximation-algorithms
> **Comments:**
> **username_0**: Crosspost from [math SE](http://math.stackexchange.com/questions/94099/)  
> **username_1**: Would you clarify what you mean by $B \circ A$ and the weight of $S$?  
> **username_0**: This is informal, for concreteness: $A,B$ are [search problems](http://en.wikipedia.org/wiki/Search_problem), $A$ is thought as an optimization problem (so the solutions carry some weight) and $B \circ A$ is composition of relations.  
> **username_1**: The answers would be a collection.  So, I would think it'd be more appropriate to make it community wiki.  
> **username_2**: Adding the big-list tag is enough, there is no need to make it community wiki IMHO.  
> **username_3**: Quote from Vijay Vazirani's book on approximation algorithm. "Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872–1970)"  

---

## 4 answers

### Answer by username_1 on 2011-12-30. Score: 13 | Accepted answer

An example from the parameterized complexity is a [kernelization](http://en.wikipedia.org/wiki/Kernelization) for the [vertex cover problem](http://en.wikipedia.org/wiki/Vertex_cover) using a theorem of Nemhauser and Trotter.

In the minimum vertex cover problem, we are given an undirected graph G, and we need to find a vertex cover of G of minimum size. A vertex cover of an undirected graph is a vertex subset that touches all edges.

Here is an exact algorithm that uses an approximation at the first phase.

Phase 1: Set up [the integer linear programming formulation of the minimum vertex cover problem](http://en.wikipedia.org/wiki/Vertex_cover#ILP_formulation). It's known (or easy to show) that a basic optimal solution of the linear programming relaxation is half-integral (i.e., every coordinate is either 0, 1, or 1/2). Such a basic optimal solution can be found by a usual polynomial-time algorithm for linear programming (or in this special case, we can formulate it as a network flow problem, so we can solve it combinatorially in polynomial time). Having such a basic optimal solution, we round it up to obtain a feasible solution to the original integer linear programming problem. Let S be the corresponding vertex subset. It's good to note that S is a 2-approximation of the given minimum vertex cover instance.

Phase 2: Find a minimum vertex cover in the subgraph induced by S (for example by an exhaustive search). A theorem by Nemhauser and Trotter states that this subgraph contains an optimal solution of the original input graph. So, the correctness of this approach follows.

You may consult [a book by Niedermeier on fixed-parameter algorithms](http://rads.stackoverflow.com/amzn/click/0198566077) for this algorithm.


---

### Answer by username_4 on 2011-12-30. Score: 12

One example is related to [tree decompositions](http://en.wikipedia.org/wiki/Tree_decomposition) and graphs of small treewidth.

Typically, *if* we are given a tree decomposition, it is fairly straightforward to apply dynamic programming to solve a given graph problem $B$ optimally. The running time depends on the width of the tree decomposition.

However, usually we are not given a tree decomposition, but we need to find it. To solve problem $B$ as fast as possible, we would like to find a tree decomposition of the smallest possible width – now this is our problem $A$.

We could try to solve problem $A$ exactly, but then we might waste too much time in part $A$. One possible approach is to use an approximation algorithm for part $A$. Then part $A$ is faster, at a cost of worse running time guarantees in part $B$.

---

Another example is related to compilers and [register allocation](http://en.wikipedia.org/wiki/Register_allocation). Assume that we have implemented an exact algorithm that solves a problem $B$ in polynomial time. The running time of the algorithm depends, in part, on how well the compiler managed to assign variables onto CPU registers – this is our problem $A$.

The solution of problem $B$ is correct even if the compiler uses an approximation algorithm to solve problem $A$; however, an approximation factor in problem $A$ affects the running time of algorithm $B$.

> **Comments:**
> **username_5**: While the treewidth example works in principle, it would be hard to execute in practice because it is very hard to approximate treewidth at all well (since you can approximate clique)  

---

### Answer by username_6 on 2011-12-30. Score: 9

An example of an approximation algorithm that converges to the exact solution would be the Ellipsoid algorithm for solving LPs - if the coefficients are rationals, then one can compute a minimum distance between two vertices of the feasible polytope. Now, the ellipsoid algorithm computes repeatedly a smaller and smaller elliposoid that must contain the optimal solution. Once the elliposoid is small enough to contain only such a single vertex, you essentially found the optimal vertex. This is why LP is weakly polynomial.

As for an example closer to your outline - consider Matousek's algorithm for finding the smallest disk containing $k$ points in the plane. The algorithm first finds a 2-approixmation (in the radius), break the plane into appropriate grid, and the solves the problem inside each grid cluster exactly, using a slow algorithm.

Finally, going further a field - many algorithm that follows the alteration technique (take a random sample - and then do some fixups to get what you want) falls into such a framework. One cute example is the algorithm for computing the median using random sampling (see the book by Motwani and Raghavan). There are many such examples - arguably many of the randomized incremental algorithms in Computational Geometry falls into this framework.


---

### Answer by username_7 on 2011-12-31. Score: 4

Many **output-sensitive** algorithms employ this technique. For example, here is a simple problem on which this technique can be used:

**Problem**. You are given an array A[1..*n*] in which each element is atmost *k* positions away from the position it would have been in if A was sorted.

For example, A[1..7] shown below could be an input array for *k* = 2.   
  
![](https://i.sstatic.net/WrNjt.jpg)

Design an algorithm to sort the array in O(*n* log *k*) time, assuming *k* is unknown.

*Problem Source: [Algo Muse](https://www.algomuse.net) Archive.*


---

