Approximation algorithms used in exact algorithms

Question

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.

Answer 1

An example from the parameterized complexity is a kernelization for the vertex cover problem 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. 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 for this algorithm.

Answer 2

One example is related to tree decompositions 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. 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$.

Answer 3

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

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

Problem Source: Algo Muse Archive.