Jakie są problemy z najlepszym współczynnikiem aproksymacji uzyskanym przez algorytm zwracający jednolicie losowe rozwiązanie?

Jakie są problemy z najlepiej znanym współczynnikiem aproksymacji osiągniętym przez algorytm zwracający jednolicie losowe rozwiązanie?

Znam jeden taki przykład problemu : w artykule „ Tight Bounds for Permutation Flow Shop Scheduling ” Viswanath Nagarajan i Maxim Sviridenko udowodnili, że losowa sekwencja zadań ma gwarancję 2 $F|perm|C_{max}$ (m- liczba maszyn in- liczba zadań), która jest obecnie najlepiej znana.$2\sqrt{min\{m,n\}}$$m$$n$

W przypadku problemów ze spełnieniem ograniczeń właściwość braku lepszego algorytmu aproksymacji niż losowe przypisanie jest znana jako oporność aproksymacyjna .

$P\neq NP$

Według Guraswami i in., FOCS '08 , unikalna hipoteza gier sugerowałaby, że nie ma algorytmu aproksymacji dla maksymalnego acyklicznego zestawu krawędzi wykreślacza znacznie lepszego niż ten, który losowo permutuje wierzchołki i zawiera krawędź, gdy wychodzi z wcześniej do późniejszego wierzchołka w permutacji (ze współczynnikiem przybliżenia 1/2).

W swoim artykule „ Optymalne przybliżenie problemu podmodularnego problemu w wartościowym modelu Oracle ” Jan Vondrak stwierdza:

$n$$(1 − \frac{1}{e})$