Algoritmos de aproximación de tiempo polinómico para la programación de máquinas: ¿cuántos problemas quedan?

22

En 1999, Petra Schuurman y Gerhard J. Woeginger publicaron el documento "Algoritmos de aproximación del tiempo polinómico para la programación de máquinas: diez problemas abiertos" . Desde entonces, que yo sepa, no han aparecido revisiones que conciernen a la misma lista de problemas. Por lo tanto, sería genial y útil si cada uno de nosotros pudiera hacer un resumen de algunos de los diez problemas abiertos y contribuir aquí.

Dai Le
fuente
No creo que esto deba hacerse CW ...
Suresh Venkat
@Suresh Venkat: ¿Cómo eliminar CW?
Oleksandr Bondarenko
Desafortunadamente, no hay forma de convertir una pregunta wiki comunitaria en una pregunta que no sea de CW. Se requiere agregar esta función al motor de Stack Exchange en: meta.stackexchange.com/questions/6821/…
Tsuyoshi Ito
Consulte también las preguntas frecuentes sobre cuándo usar la etiqueta CW: meta.cstheory.stackexchange.com/questions/225/…
Suresh Venkat

Respuestas:

16

Minimización de Makespan en máquinas idénticas bajo restricciones de precedencia

Problema abierto 1. Proporcione un resultado de aproximación 4/3 para .P | p r e c | C m a x4/3+δP|prec|Cmax

Aquí lo primero que viene a la mente es el artículo de este año de Ola Svensson "Programación limitada de dureza condicional de precedencia en máquinas idénticas". En su artículo, Ola demuestra que

"si el problema de una sola máquina es difícil de aproximar dentro de un factor de entonces el problema de la máquina paralela considerado, incluso en el caso de tiempos de procesamiento de la unidad, es difícil de aproximar dentro de un factor de , donde tiende a 0 como tiende a 0. "2 - ζ ζ ϵ2ϵ2ζζϵ

En 2008 se publicó el documento "Programación restringida de precedencia en · óptimo" que describe un algoritmo para con la relación de rendimiento, mencionado en su título. Esto mejora el algoritmo de Coffman-Graham con , donde es el número de máquinas.P| prec,pj=1| Cmax2-2(273p+1)P|prec,pj=1|Cmax p22pp

El documento "Algoritmos de aproximación para programar trabajos con restricciones de precedencia de cadena" por Jansen y Solis-Oba contiene PTAS para y, como consecuencia, para como un caso especial del primer problemaQm|chains|CmaxPm|chains|Cmax

Este año apareció Jansen y Solis-Oba (versión de revista de la anterior), que trata sobre PTAS para con un número fijo de "Esquemas de aproximación para programar trabajos con restricciones de precedencia de cadena". trabajos en cada cadena y con un número constante de trabajos en el componente conectado de cada pedido.P|chains|CmaxP|prec|Cmax

Minimización de Makespan en máquinas uniformes bajo restricciones de precedencia

El documento del año 2003 "Algoritmos de aproximación para programar trabajos con restricciones de precedencia de cadena" por Jansen y Solis-Oba contiene PTAS para .Qm|chains|Cmax

Minimización de Makespan bajo restricciones de precedencia con retrasos en la comunicación

Minimización de Makespan en máquinas no relacionadas

Minimización de Makespan en tiendas abiertas

Minimización de Makespan en tiendas de flujo

En el artículo de Nagarajan y Sviridenko de 2008 "Tight Bounds for Permutation Flow Shop Scheduling" podemos encontrar el límite superior en la relación entre el makepan óptimo y el makepan del mejor programa de permutación. Este límite es la relación de aproximación de un algoritmo propuesto, y es el mejor posible entre los algoritmos basados ​​en los límites inferiores triviales, hasta el factor . Por cierto, los algoritmos propuestos son actualmente los que tienen las mejores relaciones de aproximación.22

Minimización de Makespan en talleres

Problema abierto 7. Decida si existe un algoritmo de aproximación de tiempo polinómico para cuyo peor rendimiento sea independiente del número de máquinas y / o del número máximo de operaciones. Proporcione un resultado de aproximación 5/4 para . Proporcione un resultado de inaproximabilidad para cuyo valor crece con el número de máquinas hasta el infinito.J||Cmaxmμ5/4+δJ||CmaxJ||Cmaxm

Diseñe un PTAS para para el caso donde es parte de la entrada; o refutar la existencia de tal PTAS bajo P NP.J2||Cmaxμ

La disertación de Svensson "Aproximación de algunos problemas gráficos y de programación clásicos" contiene resultados que muestran que no puede aproximarse dentro de suponiendo y que no tiene PTAS a menos que .J||CmaxO((loglb)1ϵ)NPZTIME(2lognO(1/ϵ))J2||CmaxNPDTIME(nO(logn))

Tiempo total de finalización del trabajo sin restricciones de precedencia

Tiempo total de finalización del trabajo bajo restricciones de precedencia

Problema abierto 9. Demuestre que y no tienen algoritmos de aproximación de tiempo polinomial con garantía de rendimiento menos que P = NP.1|prec|Cj1|prec|wjCj2ϵ

En "Prueba de código largo óptimo con un bit libre", Bansal y Khot demostraron que es así, pero suponiendo una nueva variante de la conjetura de los juegos únicos.

Criterios de tiempo de flujo

Problema abierto 10. Diseñe algoritmos de aproximación de tiempo polinomial con garantías de rendimiento constante para y para .1|pmtn;rj|wjFjP|pmtn;rj|Fj

En "El tiempo de flujo ponderado no admite algoritmos " Bansal y Chan demostraron que "no admite algoritmos ". Curiosamente, los autores no citan el artículo de Schuurman y Woeginger.1 | p m t n ; r j | w j F j O ( 1 )O(1)1|pmtn;rj|wjFjO(1)

En "Minimizar el tiempo de flujo promedio: límites superior e inferior" Garg y Kumar demostraron un límite inferior en la relación de aproximación para . Más tarde, este límite se mejoró a en "Minimizing Total Flow-Time: The Unrelated Case" de Garg, Kumar y Muralidhara.P| pmtn; rj| FjΩ(logPΩ(logPloglogP)P|pmtn;rj|FjΩ(logPloglogP)

Oleksandr Bondarenko
fuente