Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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).
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."
