Was sind die Probleme mit dem besten Näherungsverhältnis, das mit einem Algorithmus erzielt wird, der eine gleichmäßig zufällige Lösung liefert?

Was sind die Probleme mit dem bekanntesten Näherungsverhältnis, das mit einem Algorithmus erzielt wird, der eine gleichmäßig zufällige Lösung liefert?

Ich kenne ein solches Beispiel für das Permutationsfluss-Ladenproblem : Viswanath Nagarajan und Maxim Sviridenko haben in der Zeitung " Tight Bounds for Permutation Flow Shop Scheduling " bewiesen, dass zufällige Abfolgen von Jobs 2 √ garantieren$F|perm|C_{max}$ (m-Anzahl von Maschinen undn-Anzahlvon Jobs), die derzeit am bekanntesten ist.$2\sqrt{min\{m,n\}}$$m$$n$

Für Bedingungserfüllungsprobleme ist die Eigenschaft, keinen besseren Annäherungsalgorithmus als eine zufällige Zuordnung zu haben, als Annäherungswiderstand bekannt .

Dies wurde in den letzten Jahren von mehreren Arbeiten untersucht, wobei einige Ergebnisse auf und andere allgemeinere Ergebnisse auf der Vermutung einzigartiger Spiele basierten. Eine gute Quelle dafür ist Per Austrins These .$P\neq NP$

Laut Guraswami et al., FOCS '08 , würde die Vermutung eines einzigartigen Spiels implizieren, dass es keinen Näherungsalgorithmus für die maximale azyklische Kantenmenge eines Digraphen gibt, der signifikant besser ist als derjenige, der die Eckpunkte zufällig permutiert und eine Kante einschließt, wenn er von einem geht früher zu einem späteren Scheitelpunkt in der Permutation (mit Näherungsverhältnis 1/2).

In seiner Arbeit " Optimale Approximation für das submodulare Wohlfahrtsproblem im Value-Oracle-Modell " behauptet Jan Vondrak:

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