¿Cuáles son los problemas con la mejor relación de aproximación lograda por el algoritmo que devuelve una solución uniforme al azar?

¿Cuáles son los problemas con la relación de aproximación más conocida lograda por un algoritmo que devuelve una solución aleatoria uniforme?

Conozco uno de esos ejemplos para el problema del taller de flujo de permutación : en el documento " Límites ajustados para la programación del taller de flujo de permutación " Viswanath Nagarajan y Maxim Sviridenko demostraron que la secuencia aleatoria de trabajos tiene garantía (número de máquinas número de trabajos) que es el más conocido actualmente.$F|perm|C_{max}$$2\sqrt{min\{m,n\}}$$m$$n$

Para problemas de satisfacción de restricciones, la propiedad de no tener un algoritmo de aproximación mejor que la asignación aleatoria se conoce como resistencia de aproximación .

Esto ha sido estudiado por varios trabajos en los últimos años, con algunos resultados basados ​​en y otros resultados más generales basados ​​en la conjetura de los juegos únicos. Una buena fuente para esto es la tesis de Per Austrin .$P\neq NP$

Según Guraswami et al, FOCS '08 , la conjetura de los juegos únicos implicaría que no existe un algoritmo de aproximación para el conjunto máximo de bordes acíclicos de un dígrafo significativamente mejor que el que permuta aleatoriamente los vértices e incluye un borde cuando va de un anterior a un vértice posterior en la permutación (con relación de aproximación 1/2).

En su artículo " Aproximación óptima para el problema de bienestar submodular en el modelo Oracle de valor ", Jan Vondrak afirma:

"Curiosamente, en el caso especial del Bienestar Submodular con jugadores iguales, la aproximación óptima de hecho se obtiene mediante una solución uniforme al azar".$n$$(1 − \frac{1}{e})$