2
$\begingroup$

A friend of mine who has done some work in approximation algorithm asked me the following question:

Can you find a (graph theory) problem with a faster approximation (deterministic) algorithm?

For example, is there a linear-time constant-factor approximation algorithm for minimum spanning tree? Or is there is asymptotically faster algorithm for maximum flow?

Added later. Let me clarify a little bit. Approximation algorithm often refers to NP-hard problem. However, the definition still makes sense for any optimization problems, including those in P.

Improve this question
$\endgroup$
2
  • $\begingroup$ Minimum Spanning Tree is not an NP-Hard problem and Polynomial time algorithms like Prim and Kruskal exist for MST. What do you mean by approximation algorithm for a problem which is not NP-Hard? $\endgroup$
    – mhsnk
    Commented Aug 4, 2016 at 6:54
  • $\begingroup$ Yes, MST is in P. There is O(|E|log|V|) algorithm solving MST. The definition of c-approximation makes sense for any optimization problem. I mean, is there is a linear-time, that is, O(|E|), algorithm which gives constant-factor approximation algorithm for MST? $\endgroup$
    – jsliyuan
    Commented Aug 4, 2016 at 7:01

2 Answers 2

Reset to default
1
$\begingroup$

One example would be maximum matching. A matching $M$ is a set of pairwise nonadjacent edges. It can be solved in polynomial time, but no linear time algorithm is known. On the other hand, the greed algorithm, that adds edges one by one if no adjacent edge has been added before, is a 2-approximation and can be implemented in linear time.

Improve this answer
$\endgroup$
1
$\begingroup$

There are approximation algorithms for the (metric) travelling salesman problem, that is, where the distances are symmetric and obey the triangle inequality.

For example, Christofides algorithm finds a path that is within a factor of 3/2 of the optimal solution length. Other special cases have even better approximations, such as the Euclidean TSP (where the vertices are points in $\mathbb{R}^d$) or the $(1, 2)$--TSP (where the edges all have length 1 or 2).

Although there is no constant factor approximation algorithm for TSP in general (without the metric assumption).

More generally this is known as the class of APX-hard or APX-complete problems. You can find more about this on the Complexity Zoo.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .