Sabemos que los programas lineales (LP) se pueden resolver exactamente en tiempo polinómico usando el método elipsoide o un método de punto interior como el algoritmo de Karmarkar. Algunos LP con un número de variables / restricciones súper polinomiales (exponenciales) también se pueden resolver en tiempo polinómico, siempre que podamos diseñar un oráculo de separación de tiempo polinómico para ellos.
¿Qué pasa con los programas semidefinitos (SDP)? ¿Qué clases de SDP se pueden resolver exactamente en tiempo polinómico? Cuando un SDP no puede resolverse exactamente, ¿podemos siempre diseñar un FPTAS / PTAS para resolverlo? ¿Cuáles son las condiciones técnicas bajo las cuales esto se puede hacer? ¿Podemos resolver un SDP con un número exponencial de variables / restricciones en tiempo polinómico, si podemos diseñar un oráculo de separación de tiempo polinómico para él?
¿Podemos resolver los SDP que ocurren en problemas de optimización combinatoria (MAX-CUT, coloreado de gráficos) de manera eficiente? Si solo podemos resolver dentro de un factor , ¿no tendrá efecto en los algoritmos de aproximación de factor constante (como 0.878 para el algoritmo MAX-CUT de Goemans-Williamson)?
Cualquier buena referencia sobre esto será muy apreciada.
Respuestas:
El método elipsoide y los métodos de punto interior también se pueden ampliar para resolver SDP. Puede consultar los textos estándar en los SDP para obtener más detalles. Aquí hay uno:
Programación semidefinida . Vandenberge y Stephen Boyd, 1996.
fuente