Una extensión clásica del problema del flujo máximo es el problema del "flujo máximo en el tiempo": se le da un dígrafo, dos de los cuales se distinguen como la fuente y el sumidero, donde cada arco tiene dos parámetros, una capacidad por -unidad-tiempo y un retraso. También se le dará un horizonte de tiempo . El objetivo es calcular un flujo a través del tiempo que se pone la cantidad máxima de material de la fuente al sumidero por el tiempo . Se puede calcular un flujo de valor máximo en tiempo polinómico mediante una inteligente reducción clásica al flujo mínimo de costo máximo.T
Estoy interesado en una extensión de este modelo donde los bordes tienen un tercer parámetro de "vida útil". Si un arco tiene una vida útil , y es el tiempo más temprano en el que se envía flujo positivo a través del arco, entonces destruimos el arco en el tiempo . Puede pensar en esto como las plataformas en Super Mario Brothers que se caen / se destruyen poco después de pisarlas, o puede pensar en ellas como baterías necesarias para alimentar los bordes, que no se pueden apagar después de encenderlas . ( Editar :) El problema de decisión es, cuando también se le da un límite inferior de valor de flujo , si uno puede programar un flujo que cumpla tanto el límite superior del horizonte de tiempo como el límite inferior de valor de flujo.t t + ℓ B
Hasta ahora puedo ver que este problema es fuertemente NP-hard (a través de 3 particiones). Pero, en realidad no sé si está en NP: ¿hay alguna garantía de una forma de expresar una solución de forma compacta? En la versión clásica, se utiliza algún tipo especial de flujo óptimo para sortear este problema.
Nota: el modelo anterior está un poco poco especificado, ya que puede permitir o no permitir el almacenamiento de flujo en los nodos, y puede tener un modelo de tiempo discreto o continuo. Resolver la pregunta para cualquiera de estos modelos sería excelente.
Respuestas:
Ha pasado mucho tiempo, pero estoy bastante seguro de que este problema está en P.
Escribí mi tesis doctoral sobre esto en 1995. Ver "Algoritmos de flujo de red dinámica eficiente" por Bruce Hoppe enviado al departamento de Cornell CS. En línea en http://dspace.library.cornell.edu/bitstream/1813/7181/1/95-1524.pdf
Vea el Capítulo 8 "Extensiones" sección 8.1 sobre "bordes mortales"
fuente
EDITAR: la respuesta es incorrecta. Hice la suposición implícita (tonta) de que cuando un flujo de ruta comienza en el tiempo sy termina en el tiempo t y pasa por el borde e, bloquea el borde e durante este tiempo. Sin embargo, eso no es verdad. Ver *.
Nota: Quizás este enfoque sea innecesariamente complicado o incorrecto. Aunque traté de verificarlo y lo escribí cuidadosamente, no pasé mucho tiempo en ello.
Suponiendo que no se permite el "almacenamiento", por ejemplo, el flujo debe transferirse inmediatamente. Sea el número de aristas y N la longitud de entrada. No especifiqué un tiempo continuo o discreto, ya que no lo tomé en consideración. Debería funcionar para el pensamiento discreto, para continuo, estoy seguro.metro norte
Luego, podemos describir la solución como un conjunto de "rutas-flujos" desde el origen hasta el sumidero. Un flujo de ruta es un cuádruple que consiste en lo siguiente: Una ruta simple P desde la fuente hasta el sumidero; Hora de inicio del flujo de ruta s ; Cantidad de flujo a través del camino a ; Tasa de rendimiento r .( P, s , a , r ) P s a r
Deje que una solución sea dada por un conjunto de flujos de ruta. Podemos verificar si la solución dada por estos flujos de ruta es correcta en el tiempo polinomial en | F | y N :F |F| N
Ahora, que 'sólo' necesidad de mostrar que el número de ruta de los flujos es polinomio en .N
Para una solución dada, podemos determinar el tiempo en que un flujo pasó por un borde y cuándo se destruyó el borde. Convierta esto en un problema con una solución equivalente: hay límites duros en cada borde cuando se puede usar y cuando no, una hora de inicio y finalización. Deje denota el conjunto de todos estos tiempos.{t1,...,tk}
Considere alguna solución no compacta y (inicialmente) un conjunto vacío de flujos de ruta. La idea es que iterativamente encontremos un flujo de ruta en la solución no compacta, lo eliminemos y lo almacenemos en nuestro conjunto de flujos de ruta.
fuente
Según tengo entendido, necesitaría almacenar solo un número por arco, que representa el instante en que el flujo comienza a enviarse a través del arco. Eso supone que después de eso, el arco queda inutilizable. Si, de lo contrario, el arco se puede usar nuevamente después de dejar de usarse, debería tener soluciones arbitrarias cercanas a las soluciones para el flujo máximo a lo largo del tiempo (ya que el flujo podría dejar de enviarse durante un período de tiempo arbitrariamente pequeño y luego comenzar a bombearse nuevamente )
fuente