Euclidean Masalah Fasilitas Lokasi Berkapasitas

Dalam Fasilitas berkapasitas Lokasi Masalah (CFLP) , kita diberi satu set klien dan satu set fasilitas potensial . Setiap klien memiliki permintaan yang harus dilayani oleh satu atau lebih fasilitas terbuka. Setiap fasilitas memiliki biaya pembukaan dan memiliki kapasitas , yang merupakan permintaan maksimum yang dapat layani fasilitas. Biaya melayani satu unit permintaan dari klien di fasilitas adalah $C$ $F$ $j \in C$ $d_j$ $i \in F$ $f_i$ $u_i$ $i$ $j$ $i$ $c_{ij}$ . Kami ingin membuka subset fasilitas dan menetapkan permintaan klien untuk membuka fasilitas sehingga tuntutan semua klien terpenuhi, tidak ada kendala kapasitas yang dilanggar dan total biaya pembukaan fasilitas dan layanan klien diminimalkan. Biaya layanan tidak negatif, simetris, dan memuaskan ketimpangan segitiga.

Arora dalam [ 1 , halaman 21] menyatakan bahwa "Arora, Raghavan dan Rao [ 2 ] memberikan PTAS untuk kasing geometrik. Mereka memperluas algoritme ke kasing kapasitansi tetapi solusi akhir dapat melanggar batasan kapasitas dengan jumlah kecil." Apa yang dia maksud dengan "jumlah kecil"? Saya kira itu berarti mereka memberikan PTAS yang melanggar batasan kapasitas dalam faktor untuk arbitrer . Apakah ini benar? $(1+\epsilon)$ $\epsilon > 0$

Ketika saya melihat [ 2 ], satu-satunya hasil terkait yang saya temukan adalah algoritma waktu untuk menemukan solusi -roksimasi untuk Masalah kapasitansi median ketika kita memiliki kapasitas yang seragam. Apakah Arora merujuk pada hasil di atas dalam [ 1 ]? $n^{O(\log^2 (n / \epsilon))}$ $(1+\epsilon)$ $k$

[ 1 ] S. Arora. Skema perkiraan untuk masalah optimasi geometris NP-keras: Sebuah survei. Dalam matematika Pemrograman, Ser. B, vol. 97, pp 43-69, 2003.

[ 2 ] S. Arora, P. Raghavan, dan S. Rao. Skema perkiraan untuk k-median Euclidean dan masalah terkait. Dalam Proc. Simposium ACM ke-30 tentang Teori Komputasi, hal 106–113, 1998.

ds.algorithms cg.comp-geom approximation-algorithms Babak Behsaz
sumber

Jawaban:

Jika saya ingat dengan benar, Anda harus memperkirakan jumlah klien yang terhubung ke setiap gerbang. Kalau tidak, Anda akan langsung mendapatkan sesuatu seperti , di mana adalah jumlah gerbang dalam subproblem. Dengan memperkirakan angka ini hingga facotr seluruh pemrograman dinamis, orang bisa mendapatkan kesalahan pada akhirnya. Itu akan menghasilkan waktu berjalan mirip dengan apa yang Anda sebutkan di atas. $O(n^{O(g)})$ $g$ $(1+\varepsilon/\log n)$ $(1+\varepsilon)$

Sariel Har-Peled
sumber

Jika saya melakukannya dengan benar, maksud Anda algoritme mereka meluas ke QPTAS dengan pelanggaran kapasitas untuk masalah lokasi fasilitas dengan kapasitas seragam. Saya ingin tahu apakah ada PTAS dengan pelanggaran untuk masalah ini.

(1 + ϵ)

$(1+\epsilon)$

(1 + ϵ)

$(1+\epsilon)$

Babak Behsaz

Itu memang pertanyaan yang menarik. Pada saat itu tampaknya orang dapat memperpanjang kertas Kolliopoulos dan Rao untuk melakukan ini.

Sariel Har-Peled

Saya memikirkan hal yang sama untuk sementara waktu, tetapi ketika saya membaca kembali bukti Teorema 4 dari [Kolliopoulos-Rao-ESA'99] beberapa bulan yang lalu, saya menemukan bahwa Anda tidak dapat menerapkan teorema itu sebagai kotak hitam. Alasannya adalah bahwa dalam bukti mereka menganggap bahwa seseorang dapat menetapkan klien ke fasilitas terbuka apa pun sementara dalam kasus kapasitansi Anda dapat melanggar kapasitas dengan modifikasi ini. Mungkin ada cara sederhana di sekitar ini, saya belum banyak memikirkannya.

Babak Behsaz