Jual blok slot waktu

27

Mengingat nn slot waktu yang kk orang ingin membeli. Orang ii memiliki nilai h ( i , j ) 0h(i,j)0 untuk setiap slot waktu . Setiap orang hanya dapat membeli satu slot waktu berturut-turut, yang bisa kosong.jj

Apakah ada algoritma waktu polinomial untuk menghitung nilai maksimum yang dapat dicapai penjual?

Tanpa kendala konsistensi, kami dapat memberikan setiap slot waktu kepada orang yang paling menghargainya. Juga, jika kita memperbaiki urutan slot waktu orang , maka pemrograman dinamis dapat digunakan untuk menyelesaikan untuk nilai maksimum dari orang yang membeli pertama waktu slot.k 0 i k 0 j nk0ik0jn

pengguna11550
sumber

Jawaban:

9

Diberikan 3CNF dengan klausa pada variabel . Misalkan dan muncul di rumus masing-masing paling kali .ϕ 1 , , ϕ k x 1 , , x n x i ¯ x i k iϕ1,,ϕkx1,,xnxixi¯¯¯¯¯ki

Kami merancang DAG berwarna yang simpulnya terdiri dari tiga bagian:GG

  • "Penugasan" simpul dan , , . Warnai dengan "color" , dan dengan .v i ( j ) ˉ v i ( j ) 1 i n 1 j k ivi(j)v¯i(j)1in1jki v i ( j ) x i ( jvi(j) )xi(j)ˉvi(j)v¯i(j)¯xi(j)xi¯¯¯¯¯(j)
  • "Klausul" simpul w i ( j ) , 1 i k , j = 1 , 2 , 3 . Warna w i ( j ) dengan warna x i ( j ) (atau ¯ x i ( j ) ) jika ¯ x i (atau , resp.) Adalah -th literal dari klausawi(j)1ikj=1,2,3wi(j)xi(j)xi¯¯¯¯¯(j)xi¯¯¯¯¯xixijjϕiϕi , dan itu adalah klausa ke- mengandung literal ini.jj
  • "Potong" simpul . Warnai mereka dengan warna berbeda yang berbeda dari atas.s=s0,s1,,sn,sn+1,sn+k=ts=s0,s1,,sn,sn+1,sn+k=t

Tepi meliputi:

  • 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
  • dan s n + i - 1 w i ( j ) , w i ( j ) s n + i .sn+i1wi(j)wi(j)sn+i

Misalnya, dari 3CNF ( x 1x 2¯ x 3 ) ( x 1¯ x 2x 3 ) grafik berikut dibuat (Arah tepi dari kiri ke kanan). (x1x2x3¯¯¯¯¯)(x1x2¯¯¯¯¯x3)enter image description here

Sekarang tidak sulit untuk melihat bahwa 3CNF asli satisfiable jika dan hanya jika ada s - t path dengan warna vertex yang berbeda di G .stG

(Ngomong-ngomong, itu adalah produk sampingan bahwa keberadaan s - t path dengan berbagai warna titik dalam DAG berwarna adalah NP-hard . Saya tidak menemukan banyak literatur tentang masalah ini dalam perspektif komputasi. Jika Anda tahu, tolong komentar!)stNP-hard

Jadi apa hubungan antara masalah G dan OP? Secara intuitif apa yang akan kita lakukan adalah merancang matriks h , sehingga setiap warna dipetakan ke baris (yang adalah orang), dan ujungnya dipetakan ke kolom berturut-turut (slot waktu). Oleh karena itu penjadwalan maksimum, yang pada dasarnya bergerak dari kiri ke kanan dalam matriks, sesuai dengan jalur s - t .Ghst

Matriks kami h memiliki 2 n + 1 + Σ i 2 k i + k kolom, dengan indeks mulai dari 0 . Dalam berikut constrcution X merupakan Y dua nilai memuaskan 1 « X « Y . Rasio X / 1 , Y / X dapat menjadi kekuatan besar k dan n . Mari K i = 2 i + 2 Σ i jh2n+1+i2ki+k0XY1XYX/1,Y/Xkn= 1 ki.Ki=2i+2ij=1ki

  • Untuk setiap s i , 0 i n , misalkan h ( s i , K i ) = h ( s i , K i - k i - 1 ) = h ( s i , K i + k i + 1 + 1 ) = Y (jika koordinat ada, sama di bawah).si0inh(si,Ki)=h(si,Kiki1)=h(si,Ki+ki+1+1)=Y
  • Untuk setiap x i ( j ) , misalkan h ( x i ( j ) , K i - 1 + j ) = X ; Untuk setiap ¯ x i ( j ) , biarkan h ( ¯ x i ( j ) , K i - 1 + k i + 1 + j ) = X .xi(j)h(xi(j),Ki1+j)=Xxi¯¯¯¯¯(j)h(xi¯¯¯¯¯(j),Ki1+ki+1+j)=X
  • Untuk setiap ϕ i , 1 i k dan literal x dalam klausa ϕ i , misalkan h ( x , K n + i ) = 1 .ϕi1ikxϕih(x,Kn+i)=1
  • Semua entri lainnya adalah 0.

Sebagai contoh, untuk contoh grafik di atas matriks yang sesuai adalah enter image description here

Sekarang kita mengklaim: yang 3CNF asli satisfiable jika dan hanya jika nilai maksimum adalah ( 2 n + 1 ) Y + Σ i k i X + k .(2n+1)Y+ikiX+k

Pertimbangkan penjadwalan yang mencapai nilai maksimum. Karena ada persis ( 2 n + 1 ) kolom di h mengandung Y , mereka semua harus ditutupi. Untuk kolom K i + k i + 1 yang memiliki dua pilihan Y , misalkan penjadwalan memberikannya ke s i . Karena kolom K i harus ditugaskan ke s i , oleh konsistensi kita harus kehilangan kolom K i + 1 hingga K i + k(2n+1)hYKi+ki+1YsiKisiKi+1i . Hal yang sama terjadi jika penjadwalan menetapkan kolom K i + k i + 1 ke s i + 1 .Ki+kiKi+ki+1si+1

Oleh karena itu, dalam rangka untuk memiliki nilai Σ i k i X , kita harus pilih semua sisa tersedia X 's dalam matriks, yang sesuai dengan tugas pada variabel. Jadi nilai sisa k dapat dicapai jika dan hanya jika penugasan memenuhi setiap klausa.ikiXXk

Sebagai kesimpulan, menentukan nilai maksimum penjadwalan hukum adalah NP-hard . Mungkin itu sebabnya semua upaya kami sebelumnya untuk menemukan algoritma gagal.NP-hard

Willard Zhan
sumber
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 ssissi with cost 0.
    • An edge tittit 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 ii has a single edge leaving sisi with a flow of 1 and a single edge arriving at titi with a flow of 1, and all other edges incident on either sisi or titi have 0 flow. Let these flow-1 edges for person ii be sivjsivj 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.

j_random_hacker
sumber
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