Продажа блоков временных интервалов

Учитывая временных интервалов, которые хотят купить k человек. Человек i имеет значение h ( i , j ) ≥ 0 для каждого временного интервала j . Каждый человек может купить только один последовательный блок временных интервалов, который может быть пустым.$n$$k$$i$$h(i,j)\geq 0$$j$

Существует ли алгоритм полиномиального времени для расчета максимального значения, которого может достичь продавец?

Без ограничения последовательности мы можем дать каждому временному интервалу человека, который ценит его больше всего. Кроме того, если мы фиксируем порядок временных интервалов людей, то динамическое программирование может использоваться для определения максимального значения первых 0 ≤ i ≤ k людей, покупающих первые 0 ≤ j ≤ n временных интервалов.$k$$0\le i \le k$$0\le j \le n$

Для 3CNF с предложениями по переменным x 1 , … , x n . Предположим, что x i и ¯ x i появляются в формуле не более k i раз соответственно.$\phi_1,\ldots,\phi_k$$x_1,\ldots,x_n$$x_i$$\overline{x_i}$$k_i$

Мы разрабатываем цветной DAG , вершины которого состоят из трех частей:$G$

• "Назначение" вершины и ˉ v я ( J ) , 1 ≤ я ≤ N , 1 ≤ J ≤ K I . Цвет v я ( J ) с "цветом" х I ( J ) , и ˉ v я ( J ) с ¯ х я ( J ) .$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)$
• Вершины «пункта» , 1 ≤ i ′ ≤ k , j ′ = 1 , 2 , 3 . Цвет ж я ' ( J ' ) с цветом х I ( J ) (или ¯ х я ( J ) ) , если ¯ х я (или х I , соотв.) Является J $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'$-ый литерал предложения , и это j-й оператор, содержащий этот литерал.$\phi_{i'}$$j$
• «Вырезать» вершины . Раскрасьте их разными цветами, отличными от приведенных выше.$s=s_0,s_1,\ldots,s_n, s_{n+1},\ldots s_{n+k}=t$

Края включают в себя:

• , v i ( j ) v i ( j + 1 ) , v i ( k i ) s i ;$s_{i-1}v_i(1)$$v_i(j)v_i(j+1)$$v_i(k_i)s_i$
• , ˉ v я ( J ) ˉ v я ( J + 1 ) , ˉ v я ( K I ) Š я ;$s_{i-1}\bar{v}_i(1)$$\bar{v}_i(j)\bar{v}_i(j+1)$$\bar{v}_i(k_i)s_i$
• и , w i ′ ( j ′ ) s n + i ′ .$s_{n+i'-1}w_{i'}(j')$$w_{i'}(j')s_{n+i'}$

Так , например, из 3CNF следующий график строится (Краевые направления слева направо). $(x_1 \vee x_2 \vee \overline{x_3})\wedge(x_1 \vee \overline{x_2}\vee x_3)$

Теперь нетрудно видеть, что исходная 3CNF выполнима тогда и только тогда, когда в G существует путь - t с разными цветами вершин .$s$$t$$G$

(Кстати, побочным продуктом является то, что существование - t пути с разными цветами вершин в цветном DAG является NP-трудным . Я не нашел много литературы по этой проблеме в вычислительной перспективе. Если вы знаете, пожалуйста, комментарий!)$s$$t$$\textsf{NP-hard}$

Так, какова связь между и проблемой OP? Интуитивно понятно, что мы собираемся сделать, это спроектировать матрицу h , чтобы каждый цвет отображался в строке (которая является человеком), а края - в последовательные столбцы (временные интервалы). Следовательно, максимальное планирование, которое в основном происходит слева направо в матрице, соответствует s - t пути.$G$$h$$s$$t$

Наша матрица имеет 2 n + 1 + ∑ i 2 k i + k столбцов с индексами, начинающимися с 0 . В следующем constrcution X Y два значения удовлетворяют 1 « X « Y . Отношения X / 1 , Y / X могут быть большими степенями k и n . Пусть K i = 2 i + 2 ∑ i $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$

• Для каждого , 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 ) = Y (если координата существует, то же самое ниже).$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$
• Для каждого пусть h ( x i ( j ) , K i - 1 + j ) = X ; Для каждого ¯ х я ( J ) , пусть ч ( ¯ х я ( J ) , К я - 1 + K я + 1 + J ) = Х .$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$
• Для каждого , 1 ≤ i ′ ≤ k и литерала x в предложении ϕ i ′ , пусть h ( x , K n + i ′ ) = 1 .$\phi_{i'}$$1\leq i'\leq k$$x$$\phi_{i'}$$h(x,K_n+i')=1$
• Все остальные записи равны 0.

Например, для приведенного выше примера графика соответствующая матрица

Теперь мы утверждаем: исходное 3CNF выполнимо тогда и только тогда, когда максимальное значение равно .$(2n+1)Y+\sum_i k_iX+k$

Рассмотрим планирование достижения максимального значения. Поскольку в h есть ровно столбцов, содержащих Y , все они должны быть покрыты. Для столбца K i + k i + 1, который имеет два варианта выбора Y , предположим, что планирование назначает его для s i . Поскольку столбец K i должен быть присвоен s i , по последовательности мы должны потерять столбцы K i + 1 до K i + $(2n+1)$$h$$Y$$K_i+k_i+1$$Y$$s_i$$K_i$$s_i$$K_i+1$ . То же самое происходит, если планирование назначает столбец K i + k i + 1 для s i + 1 .$K_i+k_i$$K_i+k_i+1$$s_{i+1}$

Поэтому, чтобы иметь значение , мы должны выбрать все остальные доступные X в матрице, что соответствует назначению на переменные. Таким образом, остальное значение k достижимо тогда и только тогда, когда присваивание удовлетворяет каждому условию.$\sum_i k_iX$$X$$k$

В заключение, решение о максимальной стоимости юридического планирования в . Может быть, поэтому все наши предыдущие попытки найти алгоритм потерпели неудачу.$\textsf{NP-hard}$

Это решение имеет проблемы и будет удалено в ближайшее время; см. комментарий templatetypedef.

Вы можете решить это за полиномиальное время, используя поток минимальных затрат . В дальнейшем все ребра имеют единичную емкость.

• Создайте исходную вершину и целевую вершину t . Мы отправим k единиц потока от s до t .$s$$t$$k$$s$$t$
• Создайте вершин v 0 , … , v n, чтобы представить моменты времени между слотами, и направленный край v j v j + 1 для каждого 0 ≤ j < n со стоимостью 0.$n+1$$v_0, \dots, v_n$$v_jv_{j+1}$$0 \le j < n$
• $i$
  • $s_i$$t_i$
  • $0 \le j < n$$s_i$$v_j$$\Sigma_{k=1}^j{h(i,k)}$$j=0$
  • $1 \le j \le n$$v_j$$t_i$$-\Sigma_{k=1}^j{h(i,k)}$
  • $ss_i$
  • $t_it$

$i$$s_i$$t_i$$s_i$$t_i$$i$$s_iv_j$$v_kt_i$$k \ge j$$v$$k = j$$i$$i$$j+1, \dots, k$

$s$$j+1, \dots, k$$v$

$h(i, j)$