Aliran Super Mario di NP?

Satu ekstensi klasik dari masalah aliran-max adalah masalah "aliran-max dari waktu ke waktu": Anda diberi digraf, dua simpul yang dibedakan sebagai sumber dan wastafel, di mana setiap busur memiliki dua parameter, kapasitas-per -unit-waktu dan penundaan. Anda juga diberi waktu horizon . Tujuannya adalah untuk menghitung aliran dari waktu ke waktu yang mendapatkan jumlah maksimum bahan dari sumber ke wastafel saat . Aliran nilai maksimum dapat dihitung dalam waktu polinomial dengan reduksi klasik yang cerdik ke aliran-min minimum. $T$ $T$

Saya tertarik pada ekstensi untuk model ini di mana ujung memiliki parameter "rentang hidup" ketiga. Jika busur memiliki rentang hidup , dan adalah waktu paling awal di mana aliran positif dikirim melalui busur, maka kami menghancurkan busur pada waktu . Anda dapat menganggap ini sebagai seperti platform di Super Mario Brothers yang jatuh / hancur tak lama setelah Anda menginjaknya, atau Anda dapat menganggapnya sebagai baterai yang diperlukan untuk memberi daya pada tepi, yang tidak dapat dimatikan setelah dihidupkan . ( Sunting :) Masalah keputusannya adalah, ketika juga diberi nilai aliran batas bawah , apakah seseorang dapat menjadwalkan pertemuan aliran baik cakrawala waktu batas atas dan nilai aliran batas bawah. $\ell$ $t$ $t+\ell$ $B$

Sejauh ini saya bisa melihat bahwa masalah ini sangat NP-hard (via 3-partisi). Tapi, saya tidak benar-benar tahu apakah itu ada di NP: apakah ada jaminan cara untuk mengekspresikan solusi secara kompak? Dalam versi klasik, beberapa tipe khusus dari aliran optimal digunakan untuk menghindari masalah ini.

Catatan: model di atas sedikit kurang spesifik, karena Anda dapat mengizinkan atau melarang penumpukan aliran pada node, dan Anda mungkin memiliki model waktu diskrit atau yang berkelanjutan. Menyelesaikan pertanyaan untuk salah satu model ini akan sangat baik.

ds.algorithms graph-algorithms network-modeling max-flow-min-cut daveagp
sumber

Saya tidak yakin saya mengerti. Mengapa ada masalah dalam mengekspresikan rencana aliran tertentu secara kompak dan memverifikasi bahwa total aliran setidaknya F dalam waktu poli?

Suresh Venkat

Anda mungkin berpikir bagaimana membuktikan bahwa output dari masalah optimisasi, yang outputnya adalah alur waktunya, dapat diperiksa untuk optimalitasnya dalam waktu poli. Namun, sering orang menunjukkan bahwa masalah keputusan hanya dengan jawaban ya / tidak ada dalam NP, dan masalah optimisasi yang memaksimalkan beberapa fungsi seperti aliran biasanya berubah menjadi masalah keputusan dengan menambahkan nilai terikat B yang lebih rendah ke input, dan masalah keputusan menjadi "Apakah ada solusi dengan nilai setidaknya B?"

andy_fingerhut

Suresh: katakanlah dalam model diskrit, cara alami untuk mengekspresikan rencana aliran mengambil bilangan bulat

untuk setiap busur, tetapi ini bukan polinomial, hanya pseudo-polinomial dalam ukuran input. Dalam model kontinu sama saya tidak melihat cara kompres ini.

T

$T$

daveagp

Andy: Anda benar, dalam istilah formal lebih baik bagi saya untuk menyatakan ini sebagai masalah keputusan dengan memiliki nilai batas bawah selain cakrawala waktu, maka itu adalah sesuatu yang dapat kita tanyakan jika terletak pada NP.

daveagp

@daveagp: Apakah Anda mencoba kekerasan PSPACE, misalnya mengurangi QBF untuk masalah Anda?

Yoshio Okamoto

Jawaban:

Sudah lama tapi saya cukup yakin masalah ini ada di P.

Saya menulis disertasi PhD tentang hal ini pada tahun 1995. Lihat "Algoritma Aliran Jaringan Dinamis Efisien" oleh Bruce Hoppe yang diajukan ke departemen Cornell CS. Online di http://dspace.library.cornell.edu/bitstream/1813/7181/1/95-1524.pdf

Lihat Bab 8 "Ekstensi" bagian 8.1 tentang "tepi fana"

Bruce Hoppe
sumber

"Malam itu gelap dan bergejolak. Jack berbaring tak bergerak di kabinnya - tidak bergerak kecuali perutnya, yang berputar-putar di perutnya seperti naik karnaval gila ..." (halaman xiii, di mana penulis membahas aplikasi praktis).

Neal Young

Kutipan yang bagus, Neal! :) BTW daveagp membuat poin bagus tentang kebutuhan ruang pseudo-polinomial untuk menyimpan "aliran" yang menjawab pertanyaan keputusan. Bagaimana tidak hanya menemukan aliran optimal tetapi juga menyatakan bahwa aliran dalam P adalah bab 1-7 dari disertasi saya

Bruce Hoppe

Luar biasa! Saya akhirnya membaca semua ini. Setelah kami memperbaiki aliran waktu pertama mencapai tepi, membuktikan kelayakan jaringan dengan waktu mulai dan akhir yang dihasilkan adalah dalam P (dengan asumsi penahanan diizinkan), dan karena itu masalah aslinya ada di NP: sertifikat berukuran polinom kami mencantumkan waktu mulai untuk setiap tepi. Karena itu Super Mario menjalankan NP-sepenuhnya. Pertanyaan acak: apakah melarang penahanan mengubah apa pun? apakah ada algoritma aproksimasi yang layak?

daveagp

EDIT: jawabannya SALAH. Saya membuat asumsi implisit (konyol) bahwa ketika alur-jalan dimulai pada waktu s dan berakhir pada waktu t dan melewati tepi e, ia memblokir tepi e untuk durasi ini. Namun, ini tidak benar. Lihat *.

Catatan: Mungkin pendekatan ini rumit dan tidak perlu. Meskipun saya memang mencoba memverifikasi, dan menuliskannya dengan hati-hati - saya tidak menghabiskan banyak waktu untuk itu.

Dengan asumsi `penimbunan 'tidak diperbolehkan misalnya aliran harus segera ditransfer. Biarkan menunjukkan jumlah tepi dan $m$ $N$ panjang input. Saya tidak menentukan waktu kontinu atau diskrit, karena saya tidak mempertimbangkannya. Ini harus bekerja untuk pemikiran yang berbeda, untuk yang berkelanjutan, saya yakin.

$(P,s,a,r)$ $P$ $s$ $a$ $r$ .

$F$ $|F|$ $N$

$e$ $t$ $e$ $t$ $e$
$T$
Untuk setiap sisi kami dapat memverifikasi apakah jalur-jalan melewati setelah itu dihancurkan atau tidak.
$B$

$N$ .

$\{t_1,...,t_k\}$ menunjukkan set semua waktu ini.

Pertimbangkan beberapa solusi non-kompak dan (awalnya) serangkaian jalur kosong. Idenya adalah bahwa kita secara iteratif menemukan jalur-aliran dalam solusi non-padat, menghapusnya dan menyimpannya di rangkaian jalur-jalan kami.

$t_i$ $t_j$ $i<j$ $t_p$ $t_q$ $[t_p,t_q] \subseteq [t_i,t_j]$ $F_{i,j}$ $t_j$ $t_j$ dengan sifat-sifat seperti dijelaskan di atas.

$[i,j]$ $[t_i,t_j]$ $[t_{i+1},t_{j-1}]$ $|F_{s,t}| \leq m$

$F_{t_i,t_j}$ starts before $t_{i+1}$ and ends after $t_{j-1}$ . Therefore, the must overlap in time that they use a certain edge. Since the throughput is maximized for the path-flow, there must be an edge where it is tight.

From this follows that $\sum_{i,j \in [k]} | F_{i,j} |\leq c m^3$ for some constant $c$ and the claim that it's in NP follows.

Ruub
sumber

To me the decomposition bound looks faulty, I'll try to give an illustrative counterexample. Suppose the network is just one source->sink edge of capacity 100, delay 0, lifespan 100. Now consider this flow schedule: in time interval [0, 1) send flow at a rate of 1; in [1, 2) at a rate of 2, etc up to rate 100 in [99, 100). Any decomposition needs >=100 paths-flows which contradicts your claim as I understand it. I should mention that Ford and Fulkerson avoid this obstacle in their classical solution (without life-spans) by considering a specific type of optimal solution, not an arbitrary one.

daveagp

This can probably be avoided by also maximizing the 'lifespan' of the flow, but there is another problem in the proof, I've editted it to make it clear.

Ruub

The way I understand it, you would need to store only one number per arc, representing the instant at which flow begins to be sent through the arc. That is assuming that after that, the arc is rendered unusable. If, otherwise, the arc can be used again after it stops being used, it should have solutions arbitrarily close to solutions to maximum flow over time (since the flow could stop being sent for an arbitrarily small amount of time and then start being pumped again).

Leandro M.
sumber

I cannot understand what your claim is.

Tsuyoshi Ito

I don't think this is correct. For example, imagine a network with three nodes, the source s, the terminal t, and another node v, with three arcs a1 = (s,v), a2 = (s,v), a3 = (v,t). Capacities of the arcs are all 1, and the traveling times are set to be 0 for a1 and a3, and 100 for a2. The life-spans are 1 for a1, and 1000 for a2 and a3. Then, at time 0 one can send one unit of flow through a1 and a3 from s to t, and starts sending one unit of flow through a2. During time 1 to 99, a3 carries no flow, since a1 is gone, but at time 100, flow through a2 arrives at v, and a3 is used again.

Yoshio Okamoto

If I understand correctly, you claim in part that once the birth/death times of the edges are fixed, the remaining problem can be solved using the classical max-flow over time approach, but I do not see how this is the case.

daveagp

@Yoshio: In that case, if, instead of beginning to send one unit of flow along a2 immediately, you stopped sending flows altogether, after an arbitrarily short amount of time a1 could be used once more, and that would yield a better solution.

Leandro M.

@Dave: no, that's not exactly what I claim. What I'm saying is that either each arc can be used only a finite number of times, or the solutions to the problem should arbitrarily approximate the solutions to max-flow-over-time. I am concerned about the details of the problem definition, in short.

Leandro M.