Sprzedawanie bloków czasu


27

Biorąc pod uwagę nn przedziałów czasowych, które kk ludzie chcą kupić. Osoba ii ma wartość h ( i , j ) 0h(i,j)0 dla każdej szczeliny czasowej jj . 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 kk osób, wówczas można zastosować programowanie dynamiczne, aby uzyskać maksymalną wartość pierwszych 0 i k0ik osób kupujących pierwsze 0 j n0jn przedziałów czasowych.

Odpowiedzi:


9

Biorąc pod uwagę 3CNF z klauzulami ϕ 1 , , ϕ kϕ1,,ϕk na zmiennych x 1 , , x nx1,,xn . Załóżmy, że zarówno x Ixi i Ż x ixi¯¯¯¯¯ pojawia się we wzorze najwyżej k ıki czasach odpowiednio.

Projektujemy kolorowy DAG G,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 ) .vi(j)v¯i(j)1in1jkivi(j)xi(j)v¯i(j)xi¯¯¯¯¯(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 wi(j)1ikj=1,2,3wi(j)xi(j)xi¯¯¯¯¯(j)xi¯¯¯¯¯xij-ty literał klauzuli ϕ i , i jest to j -ta klauzula zawierająca ten literał.ϕij
  • „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=s0,s1,,sn,sn+1,sn+k=t

Krawędzie obejmują:

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

Na przykład z 3CNF ( x 1x 2¯ x 3 ) ( x 1¯ x 2x 3 ) budowany jest następujący wykres (kierunki krawędzi są od lewej do prawej). (x1x2x3¯¯¯¯¯)(x1x2¯¯¯¯¯x3)enter image description here

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

(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!)stNP-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 .Ghst

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 jh2n+1+i2ki+k0XY1XYX/1,Y/Xkn= 1 ki.Ki=2i+2ij=1ki

  • 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).si0inh(si,Ki)=h(si,Kiki1)=h(si,Ki+ki+1+1)=Y
  • For each xi(j)xi(j), let h(xi(j),Ki1+j)=Xh(xi(j),Ki1+j)=X; For each ¯xi(j)xi¯¯¯¯¯(j), let h(¯xi(j),Ki1+ki+1+j)=Xh(xi¯¯¯¯¯(j),Ki1+ki+1+j)=X.
  • For each ϕiϕi, 1ik1ik and a literal xx in the clause ϕiϕi, let h(x,Kn+i)=1h(x,Kn+i)=1.
  • All the other entries are 0.

For example, for the above example graph the corresponding matrix is enter image description here

Now we claim: the original 3CNF is satisfiable if and only if the maximum value is (2n+1)Y+ikiX+k(2n+1)Y+ikiX+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 + k(2n+1)hYKi+ki+1YsiKisiKi+1i . To samo dzieje się, jeśli szeregowanie przypisze kolumnę K i + k i + 1 do s i + 1 .Ki+kiKi+ki+1si+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ę.ikiXXk

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ę.NP-hard


But, in the example matrix, if i pick ¯x1x1¯¯¯¯¯ ¯x2x2¯¯¯¯¯ and x3x3 i still can get to the objective. What i´m doing wrong? Also the XX in ¯x1(1)x1¯¯¯¯¯(1) should be one column to the right and the XX in ¯x1(2)x1¯¯¯¯¯(2) should be one column to the left
rotia

@rotia Yes, and that means on the left you must pick x1,x2,¯x3x1,x2,x3¯¯¯¯¯ to have 4X4X. So that corresponds to a satisfying assignment x1=x2=1,x3=0x1=x2=1,x3=0.
Willard Zhan

Can you clarify what "Suppose kiki larger one in the two numbers of appearances of literals xixi and ¯xixi¯¯¯¯¯." means? What is the number of appearance of a literal? Is that something about where it appears in the clauses/formula, or is it how many times it appears in the formula? Is kiki a literal or a number?
D.W.

@D.W. kiki is a number. My expression was indeed quite not clear; I've edited it.
Willard Zhan

@WillardZhan Yes. But if i pick those variables i can get to a value that is bigger than the one in the formula. For instance, i set Y=60Y=60 and X=7X=7, according to the formula i should get only to 450 points (assuming kk is the number of clauses). But, by choosing x1,x2,¯x3x1,x2,x3¯¯¯¯¯ i can get to 452 points by picking the four ones at the right
rotia

3

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 ss, and a target vertex tt. We will send kk units of flow from ss to tt.
  • Create n+1n+1 vertices v0,,vnv0,,vn to represent the time points between slots, and a directed edge vjvj+1vjvj+1 for each 0j<n0j<n with cost 0.
  • For each person ii, create the following:
    • A sub-source vertex sisi and a sub-sink vertex titi.
    • For every 0j<n0j<n, an edge from sisi to vjvj having cost Σjk=1h(i,k)Σjk=1h(i,k) (which we take to be 0 if j=0j=0).
    • For every 1jn1jn, an edge from vjvj to titi having cost Σjk=1h(i,k)Σjk=1h(i,k).
    • An edge ssi with cost 0.
    • An edge tit 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 si with a flow of 1 and a single edge arriving at ti with a flow of 1, and all other edges incident on either si or ti have 0 flow. Let these flow-1 edges for person i be sivj and vkti: then kj, 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,,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,,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.


3
Might this fail if some person i takes a route from their source to another person's sink and vice-versa?
templatetypedef

@templatetypedef: I believe you're right; I'll delete this answer shortly. What about this construction instead: We have the same vertices and edges as before, but now we try to "thread" a single unit of flow through a "pipeline" of people (ordered by increasing i value) by deleting all edges ssi except for ss1 and all edges tit except for tkt, and adding an edge tisi+1 with huge negative cost M for each 1i<k. The Ms will force the single unit of flow to visit all k1 of these "pipeline" edges in any optimal solution.
j_random_hacker

@j_random_hacker then you are forcing an ordering of the k people.
Chao Xu

@ChaoXu: I don't think so: in any assignment of blocks to people, the assignment can be listed in increasing order by person. (Notice that nothing forbids a person i>i being assigned a block ending at j<j, where j is the first block assigned to person i.) But I have a feeling that a close relative of the problem that affected my first attempt also affects this one...
j_random_hacker

@j_random_hacker The cost of sivj would require that si to be the ith person in the optimal solution.
Chao Xu
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.