Sprzedawanie bloków czasu

Biorąc pod uwagę $n$ przedziałów czasowych, które $k$ ludzie chcą kupić. Osoba $i$ ma wartość $h(i,j)\geq 0$ dla każdej szczeliny czasowej $j$ . Każda osoba może kupić tylko jeden kolejny blok czasu, który może być pusty.

Czy istnieje algorytm wielomianowy do obliczania maksymalnej wartości, jaką sprzedawca może osiągnąć?

Bez ograniczeń związanych z konsekwencją możemy każdemu przedziałowi czasowemu dać czas, który najbardziej go ceni. Ponadto, jeśli ustalimy kolejność przedziałów czasowych $k$ osób, wówczas można zastosować programowanie dynamiczne, aby uzyskać maksymalną wartość pierwszych $0\le i \le k$ osób kupujących pierwsze $0\le j \le n$ przedziałów czasowych.

Biorąc pod uwagę 3CNF z klauzulami $\phi_1,\ldots,\phi_k$ na zmiennych $x_1,\ldots,x_n$ . Załóżmy, że zarówno $x_i$ i $\overline{x_i}$ pojawia się we wzorze najwyżej $k_i$ czasach odpowiednio.

Projektujemy kolorowy DAG $G$ którego wierzchołki składają się z trzech części:

• „Przypisanie” wierzchołków v i ( j ) i ˉ v i ( j ) , 1 ≤ i ≤ n , 1 ≤ j ≤ k i . Kolor v i ( j ) za pomocą „koloru” x i ( j ) oraz ˉ v i ( j ) za pomocą ¯ x i ( 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)$
• „Klauzula” wierzchołki w i ′ ( j ′ ) , 1 ≤ i ′ ≤ k , j ′ = 1 , 2 , 3 . Kolor w i ′ ( j ′ ) z kolorem x i ( j ) (lub ¯ x i ( j ) ), jeżeli ¯ x i (lub x i , odpowiednio.) To 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'$-ty literał klauzuli ϕ i ′ , i jest to j -ta klauzula zawierająca ten literał.$\phi_{i'}$$j$
• „Cięte” wierzchołki s = s 0 , s 1 , … , s n , s n + 1 , … s n + k = t . Pokoloruj je wyraźnymi kolorami innymi niż powyższe.$s=s_0,s_1,\ldots,s_n, s_{n+1},\ldots s_{n+k}=t$

Krawędzie obejmują:

• s i - 1 v i ( 1 ) , 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$
• 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$
• oraz s n + i ′ - 1 w i ′ ( j ′ ) , w i ′ ( j ′ ) s n + i ′ .$s_{n+i'-1}w_{i'}(j')$$w_{i'}(j')s_{n+i'}$

Na przykład z 3CNF ( x 1 ∨ x 2 ∨ ¯ x 3 ) ∧ ( x 1 ∨ ¯ x 2 ∨ x 3 ) budowany jest następujący wykres (kierunki krawędzi są od lewej do prawej). $(x_1 \vee x_2 \vee \overline{x_3})\wedge(x_1 \vee \overline{x_2}\vee x_3)$

Teraz to nie jest trudno zauważyć, że oryginalny 3CNF jest spe wtedy i tylko wtedy, jeśli istnieje s - t ścieżka z różnymi kolorami wierzchołków w G .$s$$t$$G$

(Nawiasem mówiąc, jest to produkt uboczny, że istnienie ścieżki s - t o różnych kolorach wierzchołków w kolorowym DAG jest NP-trudne . Nie znalazłem wielu literatur na temat tego problemu w perspektywie obliczeniowej. Jeśli wiesz, proszę komentarz!)$s$$t$$\textsf{NP-hard}$

Jaki jest zatem związek między problemem G i OP? Intuicyjnie zamierzamy zaprojektować macierz h , aby każdy kolor był odwzorowany na wiersz (którym jest osoba), a krawędzie zostały odwzorowane na kolejne kolumny (szczeliny czasowe). Dlatego maksymalne szeregowanie, które zasadniczo przebiega od lewej do prawej w macierzy, odpowiada ścieżce s - t .$G$$h$$s$$t$

Nasza macierz h ma 2 n + 1 + ∑ i 2 k i + k kolumn, których indeksy zaczynają się od 0 . W poniższym Constrcution X Y są dwie wartości spełniać 1 « X « Y . Stosunki X / 1 , Y / X mogą być dużymi potęgami k i n . Niech 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$= 1 ki.$K_i=2i+2\sum_{j=1}^i k_i$

• Dla każdego s i , 0 ≤ i ≤ n , niech h ( s i , K i ) = h ( s i , K i - k i - 1 ) = h ( s i , K i + k i + 1 + 1 ) = Y (jeśli współrzędna istnieje, to samo poniżej).$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$
• For each $x_i(j)$, let $h(x_i(j),K_{i-1}+j)=X$; For each $\overline{x_i}(j)$, let $h(\overline{x_i}(j),K_{i-1}+k_i+1+j)=X$.
• For each $\phi_{i'}$, $1\leq i'\leq k$ and a literal $x$ in the clause $\phi_{i'}$, let $h(x,K_n+i')=1$.
• All the other entries are 0.

For example, for the above example graph the corresponding matrix is

Now we claim: the original 3CNF is satisfiable if and only if the maximum value is $(2n+1)Y+\sum_i k_iX+k$.

Rozważ harmonogram osiągający maksymalną wartość. Ponieważ w h są dokładnie kolumny ( 2 n + 1 ) zawierające Y , wszystkie powinny być przykryte. Dla kolumny K i + k i + 1, która ma dwie opcje Y , załóżmy, że szeregowanie przypisuje ją do s i . Ponieważ kolumna K i musi być przypisana do s i , po kolei musimy utracić kolumny K i + 1 do K i + $(2n+1)$$h$$Y$$K_i+k_i+1$$Y$$s_i$$K_i$$s_i$$K_i+1$i . To samo dzieje się, jeśli szeregowanie przypisze kolumnę K i + k i + 1 do s i + 1 .$K_i+k_i$$K_i+k_i+1$$s_{i+1}$

Dlatego też, w celu uzyskania wartości Ď I k I X , musimy wybrać cała reszta dostępnego X „s w matrycy, co odpowiada cesji na zmiennych. Tak więc reszta wartości k jest osiągalna tylko wtedy, gdy przypisanie spełnia każdą klauzulę.$\sum_i k_iX$$X$$k$

Podsumowując, ustalenie maksymalnej wartości harmonogramu prawnego jest trudne . Być może dlatego wszystkie nasze poprzednie próby znalezienia algorytmu nie powiodły się.$\textsf{NP-hard}$

This solution has problems and will be deleted soon; see templatetypedef's comment.

You can solve this in polynomial time using minimum-cost flow. In the following, all edges have unit capacity.

• Create a source vertex $s$, and a target vertex $t$. We will send $k$ units of flow from $s$ to $t$.
• Create $n+1$ vertices $v_0, \dots, v_n$ to represent the time points between slots, and a directed edge $v_jv_{j+1}$ for each $0 \le j < n$ with cost 0.
• For each person $i$, create the following:
  • A sub-source vertex $s_i$ and a sub-sink vertex $t_i$.
  • For every $0 \le j < n$, an edge from $s_i$ to $v_j$ having cost $\Sigma_{k=1}^j{h(i,k)}$ (which we take to be 0 if $j=0$).
  • For every $1 \le j \le n$, an edge from $v_j$ to $t_i$ having cost $-\Sigma_{k=1}^j{h(i,k)}$.
  • An edge $ss_i$ with cost 0.
  • An edge $t_it$ with cost 0.

A minimum-cost flow in this network will have total cost equal to the negative of the best possible profit. (This cost will be negative, but that's not a problem.) There is an optimal integral solution in which every person $i$ has a single edge leaving $s_i$ with a flow of 1 and a single edge arriving at $t_i$ with a flow of 1, and all other edges incident on either $s_i$ or $t_i$ have 0 flow. Let these flow-1 edges for person $i$ be $s_iv_j$ and $v_kt_i$: then $k \ge j$, since the only paths among $v$-vertices are those that increase the subscript. If $k = j$, then person $i$ is allocated no time slots; otherwise, person $i$ is allocated the block of time slots $j+1, \dots, k$.

Intuitively, each person "gets" 1 unit of flow from $s$ and chooses a start time (edge) and end time (edge); these start and end edges are the only edges with nonzero cost in the network, and we can represent the value of a block $j+1, \dots, k$ as the difference of two prefix sums. The unit capacities on the edges between the $v$-vertices act to prevent 2 people from using the same time slot.

Interestingly, this formulation will work even if the values $h(i, j)$ may be negative.