<p>According to <a href="http://dx.doi.org/10.1109/FOCS.2008.51" rel="nofollow">Guraswami et al, FOCS '08</a>, 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).</p>

CC BY-SA 2.5
2010-12-09T00:30:53.580Z
2010-12-09T00:30:53.580Z
David Eppstein
<p>In his paper "<a href="http://www.math.princeton.edu/~jvondrak/data/submod-value.pdf">Optimal Approximation for the Submodular Welfare Problem in the Value Oracle Model</a>" Jan Vondrak asserts:</p>

<blockquote>
  <p>"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."</p>
</blockquote>

CC BY-SA 2.5
2010-12-09T01:02:49.617Z
2010-12-09T01:02:49.617Z
Oleksandr Bondarenko
<p>For constraint satisfaction problems, the property of having no better approximation algorithm than random assignment is known as <strong>approximation resistance</strong>.</p>

<p>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 <a href="http://www.cs.toronto.edu/~austrin/papers/thesis.pdf">Per Austrin's thesis</a>.</p>

CC BY-SA 2.5
2010-12-14T03:58:01.977Z
that is neat. I had no idea that such a concept existed.
Suresh Venkat
CC BY-SA 2.5
2010-12-13T15:48:18.120Z
2010-12-13T15:48:18.120Z
Boaz Barak
<blockquote>
  <p>What are the problems with the best known approximation ratio achieved by an algorithm returning a uniformly random solution? </p>
</blockquote>

<p>I know one such example for permutation flow shop problem $F|perm|C_{max}$: in the paper "<a href="http://scholar.google.com/scholar?cluster=14978066871570961423&amp;hl=en&amp;as_sdt=2001" rel="noreferrer">Tight Bounds for Permutation Flow Shop Scheduling</a>" 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.</p>

CC BY-SA 2.5
2010-12-08T23:47:22.083Z
Max3SAT? ------
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-09T00:49:54.680Z
AFAIK, Max3SAT fits here.
Oleksandr Bondarenko
<ds.algorithms><reference-request><approximation-algorithms>
What are the problems with the best approximation ratio achieved by algorithm returning uniformly random solution?
Oleksandr Bondarenko
# What are the problems with the best approximation ratio achieved by algorithm returning uniformly random solution?

(Asked by: username_0 on 2010-12-08)

> 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](http://scholar.google.com/scholar?cluster=14978066871570961423&hl=en&as_sdt=2001)" 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.

**Tags:** ds.algorithms, reference-request, approximation-algorithms

> **Comments:**
> **username_1**: Max3SAT? ------  
> **username_0**: AFAIK, Max3SAT fits here.  

---

## 3 answers

### Answer by username_3 on 2010-12-13. Score: 18 | Accepted answer

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](http://www.cs.toronto.edu/~austrin/papers/thesis.pdf).

> **Comments:**
> **username_4**: that is neat. I had no idea that such a concept existed.  

---

### Answer by username_2 on 2010-12-09. Score: 12

According to [Guraswami et al, FOCS '08](http://dx.doi.org/10.1109/FOCS.2008.51), 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).


---

### Answer by username_0 on 2010-12-09. Score: 10

In his paper "[Optimal Approximation for the Submodular Welfare Problem in the Value Oracle Model](http://www.math.princeton.edu/~jvondrak/data/submod-value.pdf)" 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."


---

