Problème de localisation des installations capacitées euclidiennes

Dans la Facilité capacitation Lieu problème (CFLP) , nous donne un ensemble de clients et un ensemble d'équipements potentiels . Chaque client a une demande qui doit être desservie par une ou plusieurs installations ouvertes. Chaque installation a un coût d'ouverture et a une capacité , qui est la demande maximale que l'installation peut desservir. Le coût de service d'une demande unitaire du client dans l'établissement est $C$ $F$ $j \in C$ $d_j$ $i \in F$ $f_i$ $u_i$ $i$ $j$ $i$ $c_{ij}$ . Nous voulons ouvrir un sous-ensemble d'installations et affecter la demande des clients aux installations ouvertes de telle sorte que les demandes de tous les clients soient satisfaites, qu'aucune contrainte de capacité ne soit violée et que le coût total de l'ouverture des installations et des services aux clients soit minimisé. Les coûts de service sont non négatifs, symétriques et satisfont l'inégalité du triangle.

Arora dans [ 1 , page 21] déclare que "Arora, Raghavan et Rao [ 2 ] donnent un PTAS pour le cas géométrique. Ils étendent l'algorithme au cas capacitif mais la solution finale peut violer les contraintes de capacité par petite quantité." Que veut-il dire par «petite quantité»? Je suppose que cela signifie qu'ils donnent un PTAS qui viole les contraintes de capacité dans le facteur pour un arbitraire . Est-ce correct? $(1+\epsilon)$ $\epsilon > 0$

Lorsque j'ai regardé dans [ 2 ], le seul résultat connexe que j'ai trouvé était un algorithme de temps pour trouver une solution approximative pour le problème de capacité capacitive lorsque nous ont des capacités uniformes. Arora fait-il référence au résultat ci-dessus dans [ 1 ]? $n^{O(\log^2 (n / \epsilon))}$ $(1+\epsilon)$ $k$

[ 1 ] S. Arora. Schémas d'approximation pour les problèmes d'optimisation géométrique NP-dur: une étude. En mathématiques. Programmation, Ser. B, vol. 97, pp 43-69, 2003.

[ 2 ] S. Arora, P. Raghavan et S. Rao. Schémas d'approximation des k-médianes euclidiennes et problèmes associés. Dans Proc. 30e ACM Symposium on Theory of Computing, pp 106–113, 1998.

ds.algorithms cg.comp-geom approximation-algorithms Babak Behsaz
la source

$O(n^{O(g)})$ $g$ $(1+\varepsilon/\log n)$ $(1+\varepsilon)$

Sariel Har-Peled
la source

(1 + ϵ)

$(1+\epsilon)$

(1 + ϵ)

$(1+\epsilon)$

C'est en effet une question intéressante. À l'époque, il semblait que l'on pouvait étendre le papier Kolliopoulos et Rao pour ce faire.

Sariel Har-Peled

Je pensais la même chose depuis un moment, mais quand j'ai relu la preuve du Théorème 4 de [Kolliopoulos-Rao-ESA'99] il y a quelques mois, j'ai trouvé que vous ne pouvez pas appliquer ce théorème comme une boîte noire. La raison en est que dans la preuve, ils supposent que l'on peut affecter un client à n'importe quel établissement ouvert tandis que dans le cas capacitif, vous pouvez violer les capacités avec cette modification. Il peut y avoir un moyen simple de contourner cela, je n'y ai pas beaucoup réfléchi.

Babak Behsaz

Problème de localisation des installations capacitées euclidiennes

Réponses: