Euklidesowy problem z pojemną lokalizacją obiektu

W instrumentu Capacitated Lokalizacja problem (CFLP) , daje nam szereg klientów oraz zestaw potencjalnych obiektów . Każdy klient ma żądanie które musi być obsługiwane przez jedno lub więcej otwartych obiektów. Każdy obiekt ma koszt otwarcia i ma pojemność , które jest popyt, że maksymalny zakład może służyć. Koszt obsługi jednej jednostki popytu klienta w obiekcie wynosi $C$ $F$ $j \in C$ $d_j$ $i \in F$ $f_i$ $u_i$ $i$ $j$ $i$ $c_{ij}$ . Chcemy otworzyć podzbiór obiektów i przypisać popyt klientom do obiektów otwartych, tak aby wymagania wszystkich klientów zostały spełnione, nie doszło do naruszenia ograniczenia wydajności, a całkowity koszt otwarcia obiektów i obsługi klientów został zminimalizowany. Koszty usługi są nieujemne, symetryczne i spełniają nierówność trójkąta.

Arora w [ 1 , strona 21] stwierdza, że „Arora, Raghavan i Rao [ 2 ] podają PTAS dla przypadku geometrycznego. Rozszerzają algorytm na przypadek pojemnościowy, ale ostateczne rozwiązanie może w niewielkim stopniu naruszać ograniczenia pojemności”. Co rozumie przez „małą ilość”? Wydaje mi się, że oznacza to, że podają PTAS, który narusza ograniczenia pojemności w ramach współczynnika dla dowolnego . Czy to jest poprawne? $(1+\epsilon)$ $\epsilon > 0$

Gdy spojrzałem na [ 2 ], jedynym pokrewnym rezultatem, który znalazłem, był algorytm czasowy do znalezienia aproksymalnego rozwiązania dla Problem pojemności medialnej, gdy mamy jednolite zdolności. Czy Arora, o której mowa powyżej, powoduje [ 1 ]? $n^{O(\log^2 (n / \epsilon))}$ $(1+\epsilon)$ $k$

[ 1 ] S. Arora. Schematy aproksymacji dla problemów związanych z optymalizacją geometryczną twardych NP: Ankieta. W matematyce. Programowanie, Ser. B, vol. 97, s. 43–69, 2003.

[ 2 ] S. Arora, P. Raghavan i S. Rao. Schematy aproksymacji dla e-klanu w mediach euklidesowych i powiązane problemy. W Proc. 30th ACM Symposium on Theory of Computing, s. 106–113, 1998.

ds.algorithms cg.comp-geom approximation-algorithms Babak Behsaz
źródło

Odpowiedzi:

Jeśli poprawnie pamiętam, musisz podać przybliżoną liczbę klientów podłączonych do każdej bramy. W przeciwnym razie od razu uzyskasz coś takiego jak , gdzie jest liczbą bramek w podproblemie. Przybliżając tę liczbę do facotr podczas programowania dynamicznego, można uzyskać błąd na końcu. Pozwoliłoby to uzyskać czasy działania podobne do powyższych. $O(n^{O(g)})$ $g$ $(1+\varepsilon/\log n)$ $(1+\varepsilon)$

Sariel Har-Peled
źródło

Jeśli dobrze to rozumiem, masz na myśli, że ich algorytm rozciąga się na QPTAS z naruszeniem pojemności przypadku problemu z jednolitą pojemnością pojemnościowego obiektu. Zastanawiam się, czy istnieje problem PTAS z naruszeniem dla tego problemu.

(1 + ϵ)

$(1+\epsilon)$

(1 + ϵ)

$(1+\epsilon)$

Babak Behsaz

To jest rzeczywiście interesujące pytanie. W tym czasie wydawało się, że można do tego rozszerzyć papier Kolliopoulos i Rao.

Sariel Har-Peled,

Przez chwilę myślałem tak samo, ale kilka miesięcy temu ponownie przeczytałem dowód Twierdzenia 4 z [Kolliopoulos-Rao-ESA'99], stwierdziłem, że nie można zastosować tego twierdzenia jako czarnej skrzynki. Powodem jest to, że w dowodzie zakładają, że można przypisać klienta do dowolnego otwartego obiektu, podczas gdy w przypadku objętym pojemnością możesz naruszać zdolności przy tej modyfikacji. Może być na to prosty sposób, nie myślałem o tym zbyt wiele.

Babak Behsaz,