Suma acumulada mínima acumulada

Considere este problema: dada una lista de conjuntos finitos, busque un orden $s_1, s_2, s_3, \ldots$ que minimice $|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots$ .

¿Hay algoritmos conocidos para esto? ¿Cuál es su complejidad? Todavía no he podido pensar en un algoritmo óptimo eficiente, pero obviamente tampoco está en NP-Hard.

Este problema en realidad está relacionado con un problema de programación conocido como "Programación restringida de precedencia para minimizar el tiempo de finalización ponderado". El problema es el siguiente: dado un conjunto de trabajos, donde cada trabajo tiene un tiempo de procesamiento (p) y un peso (w) y se define un gráfico de precedencia en los trabajos. El objetivo es programar los trabajos en una sola máquina (no preventiva) de modo que las restricciones de precedencia se estadifiquen y se minimice la suma del tiempo de finalización ponderado. El problema es NP-hard y se conoce una aproximación de 2.

Reducción del problema de suma acumulativa mínima al problema de programación restringida de precedencia: para cada elemento, cree un trabajo con p = 1, w = 0. También para cada conjunto, cree un trabajo con p = 0, w = 1. Cree el gráfico de precedencia, de modo que si el elemento , entonces correo debe ser programada antes de S . Creo que este caso especial del problema de programación también es NP-hard.$e \in S$$e$$S$

Ver los siguientes enlaces,

1) http://www.win.tue.nl/~gwoegi/papers/precsum.pdf

2) http://web.engr.illinois.edu/~chekuri/papers/dam_sched.ps

Shalmoli Gupta ya explicó que el problema general es NP-Hard, por lo que decidí investigar si algún caso especial tiene solución polinómica. Finalmente, encontré una solución al caso especial de conjuntos que representan un árbol, o más generalmente, un orden paralelo en serie por inclusión de subconjuntos con todos los conjuntos incomparables disjuntos.

Una propiedad que facilita las cosas es si la lista de conjuntos está cerrada debajo de la intersección. Si , entonces, hay un orden óptimo en el que s 1 viene antes que s 2 . Podemos suponer WLOG que el orden óptimo es una extensión lineal del orden parcial dado por la inclusión del subconjunto.$s_1 \subseteq s_2$$s_1$$s_2$

Como todos los subconjuntos de un conjunto aparecen antes en el orden, esto significa que la cantidad agregada a la suma acumulada por un conjunto determinado es fija, independientemente de dónde aparezca. Si $S$ es la lista de conjuntos, entonces el coste incremental de un conjunto es el número de elementos en s que no están en cualquier subconjunto de s que aparece en . Si el mismo conjunto aparece varias veces en S , podemos elegir arbitrariamente uno para ir primero y dejar que los otros tengan un costo de 0.$S$$S$

Esto significa que el problema es equivalente al problema del tiempo de finalización ponderado mínimo en la programación de una sola máquina con restricciones de precedencia. En este problema, dado un conjunto de trabajos con pesos y tiempos $w_j$ , y un orden parcial en los trabajos P , deseamos encontrar un orden de los trabajos que minimice el tiempo de finalización total ponderado, es decir$t_j$$P$

$\sum_{i=1}^{n} w_{j_i} \left(\sum_{k=1}^{i} t_{j_k}\right)$

sujeto a las restricciones de precedencia . El problema de conjunto acumulado mínimo con conjuntos cerrados de intersección puede convertirse en esto creando un trabajo para cada conjunto, donde cada trabajo tiene peso 1, tiempo igual al costo incremental definido anteriormente, y P es el orden dado por la inclusión del subconjunto.$P$$P$

Como resultado, este problema es NP-Hard para general también. Sin embargo, ciertas formas especiales de P pueden resolverse en tiempo polinómico.$P$$P$

Este artículo proporciona un algoritmo para el caso de las órdenes paralelas en serie P (que también incluye el caso importante de los árboles). Desafortunadamente, no pude acceder a ese documento, así que decidí intentar reinventarlo de forma independiente. Esto es lo que se me ocurrió.$O(nlogn)$$P$

Para resolver este problema, se requieren varias observaciones.

En primer lugar, en ausencia de restricciones de precedencia, la solución óptima es simplemente ordenar los trabajos para aumentar . Para simplificar, me referiré a esto como el valor del trabajo, abreviadov(j). Tenga en cuenta que dado que la clasificación esO(nlogn), es imposible hacerlo mejor que esta complejidad.$\frac{t_j}{w_j}$$v(j)$$O(nlogn)$

Regla 1 Sea y b trabajos de tal manera que a < b ∈ P y b cubran a. Si v ( a ) < v ( b ) , entonces podemos eliminar la restricción$a$$b$$a < b \in P$$v(a) < v(b)$ sin afectar el orden óptimo o el valor objetivo.$a < b$

Suponer aparece antes de a en el orden óptimo del problema relajado. Como b cubrió a originalmente, eso significa que todos los trabajos entre by a en el nuevo orden son incomparables a a y b. Pero dado que b tiene un valor más alto que a, podemos disminuir el valor objetivo intercambiando by a, una contradicción.$b$$a$

Del mismo modo, podemos eliminar la restricción en el caso de que siempre y cuando nos aseguremos de que después de ordenar por valor, rompemos los lazos al consultar las relaciones de precedencia del problema original (simplificado). Esto asegura que la solución óptima encontrada para el problema relajado es también una solución óptima para el problema original.$v(a) = v(b)$

Por lo tanto, siempre que b cubra a y , podemos simplificar el problema eliminando la restricción$v(a) \leq v(b)$ .$a < b$

Regla 2 Supongamos que sabemos que b sigue inmediatamente después de a en una solución óptima. Podemos fusionar ayb en un nuevo nodo c con y t c = t a + t b , mientras contraemos el poset P apropiadamente.$w_c = w_a + w_b$$t_c = t_a + t_b$$P$

El valor objetivo óptimo del nuevo problema difiere en una constante del valor objetivo original (específicamente ), sin embargo, esta constante no depende del orden y, por lo tanto, el orden óptimo no se ve afectado. Podemos recuperar una solución óptima para el viejo problema tomando una solución óptima para el nuevo problema y reemplazando c por a b .$w_at_b$$c$$ab$

Regla 3 Suponga que en una solución óptima para una instancia de problema, viene inmediatamente antes que b y v ( a ) > v ( b ) . Ahora supongamos que creamos una instancia de problema más grande al agregar nuevos trabajos con el nuevo poset formado a partir de series o composición paralela con el original. Siempre habrá una solución óptima para el problema más grande donde $a$$b$$v(a) > v(b)$$a$ viene inmediatamente antes que .$b$

Supongamos lo contrario. Deje que la solución óptima contenga . Dado que P se formó mediante una composición paralela en serie, sabemos que todas las x i s son incomparables con a y b . Fusiona todos los nodos x i en un nuevo nodo x ' usando la regla 2. Ahora considera v ( x ' ) . Si v ( x ′ ) ≤ v ( x ′ y $a, x_1, x_2, \ldots, b$$P$$x_i$$a$$b$$x_i$$x'$$v(x')$ entonces podemos intercambiar$v(x') \leq v(a)$$x'$$a$ sin aumentar el valor objetivo. Del mismo modo, si , podemos intercambiar x ' y b . Por lo tanto, v ( a ) < v ( x ' ) < v ( b ) . Pero v ( a ) > v ( b ) , una contradicción.$v(x') \geq v(b)$$x'$$b$$v(a) < v(x') < v(b)$$v(a) > v(b)$

Usando la regla 2 y la regla 3, ya podemos obtener un algoritmo simple pero subóptimo . Desde $O(n^2)$$P$ es un orden paralelo en serie, suponga que la entrada contiene una representación en árbol de donde cada nodo representa la composición en serie o composición paralela, y las hojas son trabajos individuales. Podemos encontrar una solución óptima con el recorrido previo del pedido del árbol manteniendo la invariante de que la solución óptima para cada subproblema es una cadena en orden de valor creciente.$P$

Suponga que es la composición en serie de subproblemas con posets P 1 y P 2 . Deje que las soluciones óptimas ordenen C 1 y C 2 . La solución óptima para P es claramente la concatenación de estas cadenas. Sin embargo, es posible que el primer trabajo en C 2 tenga un valor más bajo que el último trabajo en C 1 . Para mantener la invariante de que la solución es una cadena ordenada, utilizamos la regla 3 + la regla 2 para fusionar los puntos finales siempre que no estén ordenados.$P$$P_1$$P_2$$C_1$$C_2$$P$$C_2$$C_1$

Si es en cambio una composición paralela, simplemente tomamos las cadenas clasificadas S 1 y$P$$S_1$ y las fusionamos en una nueva cadena clasificada. Gracias a la invariante, esto es válido.$S_2$

Desafortunadamente, este algoritmo es . Para obtener un O ( n l o g $O(n^2)$algoritmo ) , necesitamos calcular las cadenas perezosamente usando la regla 1.$O(nlogn)$

Específicamente, si un subproblema contiene solo nodos donde las restricciones de precedencia son las mismas que el orden de los valores, entonces podemos olvidar las restricciones de precedencia completamente y solo mirar los valores. Esto está garantizado por el mismo invariante que garantizó que las soluciones sean cadenas ordenadas en el algoritmo anterior.

En lugar de calcular una cadena ordenada para cada subproblema, representamos la solución óptima para un subproblema como un par de montones de Fibonacci, uno de un montón mínimo y uno de un montón máximo, ambos contienen todos los trabajos en el subproblema. Esto significa que podemos extraer el elemento mínimo o máximo de la solución en tiempo logarítmico.

Como antes, hacemos un recorrido previo al pedido. Donde es una composición en serie, examinamos el trabajo máximo del primer par de almacenamiento dinámico y el trabajo mínimo del segundo par de almacenamiento dinámico. Si sus valores están fuera de orden, los sacamos y los fusionamos usando las reglas 2 y 3. Luego comparamos el trabajo recién creado con los nuevos puntos finales y continuamos apareciendo y fusionando mientras estén fuera de orden. Una vez que los puntos finales ya no tienen valores fuera de orden, podemos olvidar con seguridad la restricción de precedencia de serie gracias a la regla 1. Luego, simplemente empujamos los trabajos recién creados, si los hay, en un montón, luego fusionamos los montones para crear el par de montón que representa la solución a $P$$P$ mismo.

Para una composición paralela, simplemente fusionamos los pares de montón. El nuevo montón mínimo es la fusión del montón mínimo de cada subproblema y del mismo modo con el montón máximo. Tenga en cuenta que los montones de Fibonacci son fusionables en tiempo constante.

Una vez que tengamos un par de almacenamiento dinámico que represente la solución a todo el problema, podemos encontrar el orden de la solución real sacando el almacenamiento dinámico mínimo hasta que esté vacío. Después de eso, deshacemos todas las sustituciones de la regla 2 para obtener una solución al problema original.

Cada trabajo que se extrae de un montón se fusiona inmediatamente en un nuevo trabajo, reduciendo el recuento total del trabajo, o se emerge exactamente una vez al final. Por lo tanto, a lo sumo hay un número lineal de heap pops, lo que lleva al tiempo sobre todo. Las otras operaciones son de tiempo constante por nodo o trabajo y, por lo tanto, lineales en general.$O(nlogn)$