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

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.

• Max3SAT? ------ Dec 8 '10 at 23:47
• AFAIK, Max3SAT fits here. Dec 9 '10 at 0:49

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