12
$\begingroup$

What are the problems with the best known approximation ratio achieved by an algorithm returning a uniformly random solution?

I know one such example for permutation flow shop problem $F|perm|C_{max}$: in the paper "Tight Bounds for Permutation Flow Shop Scheduling" Viswanath Nagarajan and Maxim Sviridenko proved that random sequence of jobs have guarantee $2\sqrt{min\{m,n\}}$ ($m$-number of machines and $n$ - number of jobs) which is the best known currently.

$\endgroup$
  • 10
    $\begingroup$ Max3SAT? ------ $\endgroup$ – Tsuyoshi Ito Dec 8 '10 at 23:47
  • $\begingroup$ AFAIK, Max3SAT fits here. $\endgroup$ – Oleksandr Bondarenko Dec 9 '10 at 0:49
18
$\begingroup$

For constraint satisfaction problems, the property of having no better approximation algorithm than random assignment is known as approximation resistance.

This is has been studied by several works in the last few years, with some results based on $P\neq NP$ and other more general results based on the unique games conjecture. A good source for this is Per Austrin's thesis.

$\endgroup$
  • $\begingroup$ that is neat. I had no idea that such a concept existed. $\endgroup$ – Suresh Venkat Dec 14 '10 at 3:58
12
$\begingroup$

According to Guraswami et al, FOCS '08, the unique games conjecture would imply that there is no approximation algorithm for the maximum acyclic edge set of a digraph significantly better than the one that randomly permutes the vertices and includes an edge when it goes from an earlier to a later vertex in the permutation (with approximation ratio 1/2).

$\endgroup$
10
$\begingroup$

In his paper "Optimal Approximation for the Submodular Welfare Problem in the Value Oracle Model" Jan Vondrak asserts:

"Interestingly, in the special case of Submodular Welfare with $n$ equal players, the optimal $(1 − \frac{1}{e})$-approximation is in fact obtained by a uniformly random solution."

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