Standortproblem der euklidischen kapazitiven Einrichtung

In der Capacitated Facility Location (CFLP) werden wir eine Reihe von Kunden gegeben und eine Reihe von möglichen Einrichtungen . Jeder Client hat eine Anforderung , die von einer oder mehreren offenen Einrichtungen bedient werden muss. Jede Einrichtung hat Öffnungskosten und eine Kapazität , was der maximalen Nachfrage entspricht, die die Einrichtung bedienen kann. Die Kosten des Dienens eine Einheit Nachfrage von Client in Anlage istF j ∈ C d j i ∈ F f i u i i j i c i $C$$F$$j \in C$$d_j$$i \in F$$f_i$$u_i$$i$$j$$i$$c_{ij}$. Wir möchten eine Teilmenge von Einrichtungen öffnen und die Nachfrage von Kunden offenen Einrichtungen so zuordnen, dass die Anforderungen aller Kunden erfüllt werden, keine Kapazitätsbeschränkung verletzt wird und die Gesamtkosten für die Eröffnung von Einrichtungen und die Wartung von Kunden minimiert werden. Die Servicekosten sind nicht negativ, symmetrisch und erfüllen die Dreiecksungleichheit.

Arora in [ 1 , Seite 21] gibt an, dass "Arora, Raghavan und Rao [ 2 ] ein PTAS für den geometrischen Fall angeben. Sie erweitern den Algorithmus auf den kapazitiven Fall, aber die endgültige Lösung kann Kapazitätsbeschränkungen um einen kleinen Betrag verletzen." Was meint er mit "kleiner Menge"? Ich denke, es bedeutet, dass sie ein PTAS geben, das Kapazitätsbeschränkungen innerhalb des Faktors für ein beliebiges verletzt . Ist das richtig?ϵ > $(1+\epsilon)$$\epsilon > 0$

Als ich in [ 2 ] nachgesehen habe, war das einzige verwandte Ergebnis, das ich gefunden habe, ein Zeitalgorithmus zum Finden einer -Näherungslösung für die Kapazitiertes Median-Problem, wenn wir einheitliche Kapazitäten haben. Führt das oben erwähnte Arora zu [ 1 ]? ( 1 + ϵ ) $n^{O(\log^2 (n / \epsilon))}$$(1+\epsilon)$$k$

[ 1 ] S. Arora. Approximationsschemata für NP-harte geometrische Optimierungsprobleme: Eine Umfrage. In Mathe. Programmierung, Ser. B, vol. 97, S. 43-69, 2003.

[ 2 ] S. Arora, P. Raghavan und S. Rao. Approximationsschemata für die euklidischen k-Mediane und verwandte Probleme. In Proc. 30. ACM-Symposium zur Theorie des Rechnens, S. 106–113, 1998.

Wenn ich mich richtig erinnere, müssen Sie die Anzahl der mit jedem Gate verbundenen Clients approximieren. Andernfalls würden Sie sofort so etwas wie , wobei die Anzahl der Tore in einem Teilproblem ist. Wenn diese Zahl während der gesamten dynamischen Programmierung auf einen Faktor von angenähert wird, kann am Ende ein Fehler . Das würde zu ähnlichen Laufzeiten führen wie oben angegeben.g ( 1 + ε / log n ) ( 1 + ε $O(n^{O(g)})$$g$$(1+\varepsilon/\log n)$$(1+\varepsilon)$