Como es bien sabido, los problemas de optimización de NP-hard pueden tener muchas relaciones de aproximación diferentes, que van desde tener un PTAS hasta no ser aproximable dentro de ningún factor. En el medio, tenemos varias constantes, , p o l y ( n ) , etc.
¿Qué se sabe sobre el conjunto de posibles proporciones? ¿Podemos probar algún tipo de "jerarquía de aproximación"? Formalmente, por lo que las funciones y g ( n ) podemos probar que existe un problema con relación aproximación f ( n ) ≤ alpha < g ( n ) ?
En el caso de que , ¿existe un problema con la relación de aproximación exactamente α ?
cc.complexity-theory
approximation-hardness
Jeremy Hurwitz
fuente
fuente
Respuestas:
Hay muchos resultados sobre el conjunto de posibles relaciones, pasando de resultados como este:
para definir los problemas APX / NPO-PB-hard.
Algunas referencias:
Pero sugiero que lo mejor será verificar el Complejo Zoo porque tiene mucha más información y referencias sobre esos ejemplos, incluso Wikipedia.
fuente
Todavía creo que el comentario de Suresh debajo de la pregunta es suficiente para mostrar que cualquier relación es posible. Si no está convencido de eso, puede ver los Problemas de satisfacción de restricciones booleanas (CSP), por ejemplo.
Per Austrin y Johan Håstad, Independencia y resistencia apoyadas aleatoriamente, SIAM Journal on Computing, vol. 40, no. 1, pp. 1-27, 2011.
fuente