Venta de bloques de franjas horarias

27

Dado franjas horarias que gente quiere comprar. La persona tiene un valor para cada intervalo de tiempo . Cada persona solo puede comprar un bloque consecutivo de franjas horarias, que podrían estar vacías.nkih(i,j)0j

¿Existe un algoritmo de tiempo polinómico para calcular el valor máximo que el vendedor puede lograr?

Sin la restricción de la consecutividad, podemos asignar cada intervalo de tiempo a la persona que más lo valora. Además, si nos fijamos el orden de los intervalos de tiempo de las personas, entonces la programación dinámica se puede utilizar para resolver el valor máximo de la primera la gente que compra el primer tiempo ranurask0ik0jn

usuario11550
fuente

Respuestas:

9

Dado un 3CNF con cláusulas en las variables . Suponga que tanto como aparecen en la fórmula como máximo veces respectivamente.ϕ1,,ϕkx1,,xnxixi¯ki

Diseñamos un DAG color cuyos vértices constan de tres partes:G

  • Vértices de "asignación" y , , . Colorea con el "color" y con .vi(j)v¯i(j)1in1jkivi(j)xi(j)v¯i(j)xi¯(j)
  • "Cláusula" vértices , , . Colorea con el color (o ) si (o , resp.) Es el literal -th de la cláusula , y es la cláusula -ésima que contiene este literal.1ikj=1,2,3w i (j)xi(j) ¯ x i (j) ¯ x i xijϕ i jwi(j)1ikj=1,2,3wi(j)xi(j)xi¯(j)xi¯xijϕij
  • "Cortar" vértices . Coloréalos con colores distintos a los anterioress=s0,s1,,sn,sn+1,sn+k=t

Los bordes incluyen:

  • si1vi(1) , , ;v i ( k i ) s ivi(j)vi(j+1)vi(ki)si
  • ˉ v i ( j ) ˉ v i ( j + 1 ) ˉ v i ( k i ) s isi1v¯i(1) , , ;v¯i(j)v¯i(j+1)v¯i(ki)si
  • y , .w i ( j ) s n + i sn+i1wi(j)wi(j)sn+i

Por ejemplo, a partir de 3CNF se construye el siguiente gráfico (Las direcciones de los bordes son de izquierda a derecha). (x1x2x3¯)(x1x2¯x3)ingrese la descripción de la imagen aquí

Ahora bien, no es difícil ver que el original es 3CNF satisfiable si y sólo si hay una - camino con diferentes colores de los vértices en .t GstG

(Por cierto, es un subproducto que la existencia de ruta - con diferentes colores de vértice en DAG coloreado es . No encontré muchas publicaciones sobre este problema en perspectiva computacional. Si ya sabes, por favor comenta!)t NP-hardstNP-hard

Entonces, ¿cuál es la relación entre el problema de y OP? Intuitivamente, lo que vamos a hacer es diseñar una matriz , de modo que cada color se asigne a una fila (que es una persona), y los bordes se asignen a columnas consecutivas (intervalos de tiempo). Por lo tanto, una programación máxima, que básicamente va de izquierda a derecha en la matriz, corresponde a una ruta - .h s tGhst

Nuestra matriz tiene columnas, con índices que comienzan desde . En el siguiente constrcution un son dos valores satisfacen . Las relaciones pueden ser grandes potencias de y . Deje .2 n + 1 + i 2 k i + k 0 X Y 1 X Y X / 1 , Y / X k n K i = 2 i + 2 i j = 1 k ih2n+1+i2ki+k0XY1XYX/1,Y/XknKi=2i+2j=1iki

  • Para cada , , sea (si la coordenada existe, la misma a continuación). 0 i n h ( s i , K i ) = h ( s i , K i - k i - 1 ) = h ( s i , K i + k i + 1 + 1 ) = Ysi0inh(si,Ki)=h(si,Kiki1)=h(si,Ki+ki+1+1)=Y
  • Para cada , sea ; Para cada , dejar que .h ( x i ( j ) , K i - 1 + j ) = X ¯ x i ( j ) h ( ¯ x i ( j ) , K i - 1 + k i + 1 + j ) = Xxi(j)h(xi(j),Ki1+j)=Xxi¯(j)h(xi¯(j),Ki1+ki+1+j)=X
  • Para cada , y una literal en la cláusula , sea . 1 i k x ϕ i h ( x , K n + i ) = 1ϕi1ikxϕih(x,Kn+i)=1
  • Todas las otras entradas son 0.

Por ejemplo, para el gráfico de ejemplo anterior, la matriz correspondiente es ingrese la descripción de la imagen aquí

Ahora afirmamos: el 3CNF original es satisfactoria si y solo si el valor máximo es .(2n+1)Y+ikiX+k

Considere la programación logrando el valor máximo. Como hay exactamente columnas en contienen , todas deberían estar cubiertas. Para la columna que tiene dos opciones de , suponga que la programación la asigna a . Como la columna debe asignarse a , por la consecutividad tenemos que perder las columnas a . Lo mismo sucede si la programación asigna la columna a .h Y K i + k i + 1 Y s i K i s i K i + 1 K i + k i K i + k i + 1 s i + 1(2n+1)hYKi+ki+1YsiKisiKi+1Ki+kiKi+ki+1si+1

Por lo tanto, para tener el valor , debemos seleccionar todas las disponibles en la matriz, que corresponde a una asignación de variables. Por lo tanto, el valor de reposo de es alcanzable si y solo si la asignación satisface cada cláusula.X kikiXXk

Como conclusión, la decisión del valor máximo de una programación legal se encuentra en . Quizás es por eso que todos nuestros intentos anteriores de encontrar un algoritmo fallaron.NP-hard

Willard Zhan
fuente
Pero, en la matriz de ejemplo, si elijo y todavía puedo llegar al objetivo. ¿Qué estoy haciendo mal? También la en debe ser una columna a la derecha y la en debe ser una columna a la izquierda ¯ x 2 x3X ¯ x 1 (1)X ¯ x 1 (2)x1¯ x2¯x3Xx1¯(1)Xx1¯(2)
rotia
@rotia Sí, y eso significa que a la izquierda debes elegir para tener . Entonces eso corresponde a una asignación satisfactoria . 4 X x 1 = x 2 = 1 , x 3 = 0x1,x2,x3¯4Xx1=x2=1,x3=0
Willard Zhan
¿Puede aclarar qué "Suponga que más grande en los dos números de apariciones de los literales y ". ¿medio? ¿Cuál es el número de aparición de un literal? ¿Es eso algo acerca de dónde aparece en las cláusulas / fórmula, o es cuántas veces aparece en la fórmula? ¿Es un literal o un número? x i ¯ x i k ikixixi¯ki
DW
@DW es un número. Mi expresión no era realmente clara; Lo he editado ki
Willard Zhan
@WillardZhan Sí. Pero si elijo esas variables, puedo llegar a un valor que es más grande que el de la fórmula. Por ejemplo, establezco y , de acuerdo con la fórmula, debería llegar solo a 450 puntos (suponiendo que es el número de cláusulas). Pero, al elegir puedo llegar a 452 puntos seleccionando los cuatro a la derechaX = 7 k x 1 , x 2 , ¯ x 3Y=60X=7kx1,x2,x3¯
rotia
3

Esta solución tiene problemas y se eliminará pronto; ver el comentario de templatetypedef.

Puede resolver esto en tiempo polinómico usando flujo de costo mínimo . A continuación, todos los bordes tienen capacidad unitaria.

  • Cree un vértice de origen , y un vértice de destino . Vamos a enviar unidades de flujo de a .t k s tstkst
  • Cree vértices para representar los puntos de tiempo entre las ranuras y un borde dirigido para cada con costo 0.v 0 , , v n v j v j + 1 0 j < nn+1v0,,vnvjvj+10j<n
  • Para cada persona , cree lo siguiente: i
    • Un vértice de sub-fuente y un vértice de sub-sumidero .t isiti
    • Por cada , un borde de a tiene un costo (que consideramos 0 si ).s i v j Σ j k = 1 h ( i , k ) j = 00j<nsivjΣk=1jh(i,k)j=0
    • Por cada , un borde de a tiene un costo .v j t i - Σ j k = 1 h ( i , k )1jnvjtiΣk=1jh(i,k)
    • Una ventaja con costo 0.ssi
    • Una ventaja con costo 0.tit

Un flujo de costo mínimo en esta red tendrá un costo total igual al negativo del mejor beneficio posible. (Este costo será negativo, pero eso no es un problema). Existe una solución integral óptima en la que cada persona tiene un borde único que deja con un flujo de 1 y un borde único que llega a con un flujo de 1, y todas las demás aristas incidentes a ambos o tienen 0 flujo. Deje que estos bordes de flujo-1 para la persona sean y : luego , ya que las únicas rutas entre -vertices son aquellas que aumentan el subíndice. SiS i t iisitit i i s i v j v k t i k j v k = j i i j + 1 , , ksitiisivjvktikjvk=j, entonces a la persona se le asignan franjas horarias; de lo contrario, a la persona se le asigna el bloque de intervalos de tiempo .iij+1,,k

Intuitivamente, cada persona "obtiene" 1 unidad de flujo de elige un tiempo de inicio (borde) y un tiempo de finalización (borde); estos bordes iniciales y finales son los únicos bordes con un costo distinto de cero en la red, y podemos representar el valor de un bloque como la diferencia de dos sumas de prefijos. Las capacidades de la unidad en los bordes entre los -vertices actúan para evitar que 2 personas usen el mismo intervalo de tiempo.j + 1 , , k vsj+1,,kv

Curiosamente, esta formulación funcionará incluso si los valores pueden ser negativos.h(i,j)

j_random_hacker
fuente
3
Podría esto fallar si alguna persona toma una ruta desde su origen hasta el fregadero de otra persona y viceversa? i
templatetypedef
@templatetypedef: Creo que tienes razón; Eliminaré esta respuesta en breve. ¿Qué pasa con esta construcción en su lugar? Tenemos los mismos vértices y bordes que antes, pero ahora tratamos de "enhebrar" una sola unidad de flujo a través de una "tubería" de personas (ordenada aumentando el valor de ) eliminando todos los bordes excepto y todos los bordes excepto , y agregando un borde con un enorme costo negativo por cada . Los s obligarán a la unidad de flujo única a visitar todos los de estos bordes de "tubería" en cualquier solución óptima. s s i s s 1ississ1t k t t i s i + 1 - M 1 i < k - M k - 1tittkttisi+1M1i<kMk1
j_random_hacker
@j_random_hacker, entonces estás obligando a ordenar a las personas. k
Chao Xu
@ChaoXu: No lo creo: en cualquier asignación de bloques a personas, la asignación se puede enumerar en orden creciente por persona. (Observe que nada prohíbe que a una persona asignen un bloque que termina en , donde es el primer bloque asignado a la persona .) Pero tengo la sensación de que un pariente cercano del problema que afectó a mi primer intento también afecta a este ...j < j j ii>ij<jji
j_random_hacker
@j_random_hacker El costo de requeriría que sea ​​la ésima persona en la solución óptima. s i isivjsii
Chao Xu