10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Crosspost from math SE $\endgroup$ – sdcvvc Dec 30 '11 at 7:39
  • $\begingroup$ Would you clarify what you mean by $B \circ A$ and the weight of $S$? $\endgroup$ – Yoshio Okamoto Dec 30 '11 at 8:09
  • $\begingroup$ This is informal, for concreteness: $A,B$ are search problems, $A$ is thought as an optimization problem (so the solutions carry some weight) and $B \circ A$ is composition of relations. $\endgroup$ – sdcvvc Dec 30 '11 at 8:20
  • $\begingroup$ The answers would be a collection. So, I would think it'd be more appropriate to make it community wiki. $\endgroup$ – Yoshio Okamoto Dec 30 '11 at 14:47
  • $\begingroup$ Adding the big-list tag is enough, there is no need to make it community wiki IMHO. $\endgroup$ – Gopi Dec 30 '11 at 16:32
12
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Suresh Venkat Dec 30 '11 at 20:08
8
$\begingroup$

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 example - arguably many of the randomized incremental algorithms in Computational Geometry falls into this framework.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.