Venta de bloques de franjas horarias

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. $n$ $k$ $i$ $h(i,j)\geq 0$ $j$

¿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 ranuras $k$ $0\le i \le k$ $0\le j \le n$

algorithms optimization np-hard scheduling usuario11550
fuente

Respuestas:

Dado un 3CNF con cláusulas en las variables . Suponga que tanto como aparecen en la fórmula como máximo veces respectivamente. $\phi_1,\ldots,\phi_k$ $x_1,\ldots,x_n$ $x_i$ $\overline{x_i}$ $k_i$

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 . $v_i(j)$ $\bar{v}_i(j)$ $1\leq i\leq n$ $1\leq j\leq k_i$ $v_i(j)$ $x_i(j)$ $\bar{v}_i(j)$ $\overline{x_i}(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. $w_{i'}(j')$ $1\leq i'\leq k$ $j'=1,2,3$ $w_{i'}(j')$ $x_i(j)$ $\overline{x_i}(j)$ $\overline{x_i}$ $x_i$ $j'$ $\phi_{i'}$ $j$
"Cortar" vértices . Coloréalos con colores distintos a los anteriores $s=s_0,s_1,\ldots,s_n, s_{n+1},\ldots s_{n+k}=t$

Los bordes incluyen:

$s_{i-1}v_i(1)$ , , ; $v_i(j)v_i(j+1)$ $v_i(k_i)s_i$
$s_{i-1}\bar{v}_i(1)$ , , ; $\bar{v}_i(j)\bar{v}_i(j+1)$ $\bar{v}_i(k_i)s_i$
y , . $s_{n+i'-1}w_{i'}(j')$ $w_{i'}(j')s_{n+i'}$

Por ejemplo, a partir de 3CNF se construye el siguiente gráfico (Las direcciones de los bordes son de izquierda a derecha). $(x_1 \vee x_2 \vee \overline{x_3})\wedge(x_1 \vee \overline{x_2}\vee x_3)$

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 . $s$ $t$ $G$

(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!) $s$ $t$ $\textsf{NP-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 - . $G$ $h$ $s$ $t$

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 . $h$ $2n+1+\sum_i 2k_i+k$ $0$ $X$ $Y$ $1\ll X\ll Y$ $X/1, Y/X$ $k$ $n$ $K_i=2i+2\sum_{j=1}^i k_i$

Para cada , , sea (si la coordenada existe, la misma a continuación). $s_i$ $0\leq i\leq n$ $h(s_i,K_i)=h(s_i,K_i-k_i-1)=h(s_i,K_i+k_{i+1}+1)=Y$
Para cada , sea ; Para cada , dejar que . $x_i(j)$ $h(x_i(j),K_{i-1}+j)=X$ $\overline{x_i}(j)$ $h(\overline{x_i}(j),K_{i-1}+k_i+1+j)=X$
Para cada , y una literal en la cláusula , sea . $\phi_{i'}$ $1\leq i'\leq k$ $x$ $\phi_{i'}$ $h(x,K_n+i')=1$
Todas las otras entradas son 0.

Por ejemplo, para el gráfico de ejemplo anterior, la matriz correspondiente es

Ahora afirmamos: el 3CNF original es satisfactoria si y solo si el valor máximo es . $(2n+1)Y+\sum_i k_iX+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 . $(2n+1)$ $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}$

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. $\sum_i k_iX$ $X$ $k$

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. $\textsf{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

\bar{x_{1}}

$\overline{x_1}$

\bar{x_{2}}

$\overline{x_2}$

x_{3}

${x_3}$

X

$X$

\bar{x_{1}} (1)

$\overline{x_1}(1)$

X

$X$

\bar{x_{1}} (2)

$\overline{x_1}(2)$

rotia

@rotia Sí, y eso significa que a la izquierda debes elegir para tener . Entonces eso corresponde a una asignación satisfactoria .

x_{1}, x_{2}, \bar{x_{3}}

$x_1,x_2,\overline{x_3}$

4 X

$4X$

x_{1} = x_{2} = 1, x_{3} = 0

$x_1=x_2=1,x_3=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?

k_{i}

$k_i$

x_{i}

$x_i$

\bar{x_{i}}

$\overline{x_i}$

k_{i}

$k_i$

@DW es un número. Mi expresión no era realmente clara; Lo he editado

k_{i}

$k_i$

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 derecha

Y = 60

$Y = 60$

X = 7

$X = 7$

k

$k$

x_{1}, x_{2}, \bar{x_{3}}

$x_1,x_2,\overline{x_3}$

rotia

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 . $s$ $t$ $k$ $s$ $t$
Cree vértices para representar los puntos de tiempo entre las ranuras y un borde dirigido para cada con costo 0. $n+1$ $v_0, \dots, v_n$ $v_jv_{j+1}$ $0 \le j < n$
Para cada persona , cree lo siguiente:
- Un vértice de sub-fuente y un vértice de sub-sumidero . $s_i$ $t_i$
- Por cada , un borde de a tiene un costo (que consideramos 0 si ). $0 \le j < n$ $s_i$ $v_j$ $\Sigma_{k=1}^j{h(i,k)}$ $j=0$
- Por cada , un borde de a tiene un costo . $1 \le j \le n$ $v_j$ $t_i$ $-\Sigma_{k=1}^j{h(i,k)}$
- Una ventaja con costo 0. $ss_i$
- Una ventaja con costo 0. $t_it$

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. Si $i$ $s_i$ $t_i$ $s_i$ $t_i$ $i$ $s_iv_j$ $v_kt_i$ $k \ge j$ $v$ $k = 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 . $i$ $i$ $j+1, \dots, 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. $s$ $j+1, \dots, k$ $v$

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

j_random_hacker
fuente

Podría esto fallar si alguna persona toma una ruta desde su origen hasta el fregadero de otra persona y viceversa?

i

$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.

i

$i$

s s_{i}

$ss_i$

s s_{1}

$ss_1$

t_{i} t

$t_it$

t_{k} t

$t_kt$

t_{i} s_{i + 1}

$t_is_{i+1}$

- M

$-M$

1 \leq i < k

$1 \le i < k$

- M

$-M$

k - 1

$k-1$

j_random_hacker

@j_random_hacker, entonces estás obligando a ordenar a las personas.

k

$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 ...

i^{'} > i

$i' > i$

j^{'} < j

$j' < j$

j

$j$

i

$i$

j_random_hacker

@j_random_hacker El costo de requeriría que sea la ésima persona en la solución óptima.

s_{i} v_{j}

$s_iv_j$

s_{i}

$s_i$

i

$i$

Chao Xu