In the Capacitated Facility Location Problem (CFLP), we are given aset of clients $C$ and a set of potential facilities $F$. Each client $j \in C$ has a demand $d_j$ that must be served by one or more open facilities. Each facility $i \in F$ has an opening cost $f_i$ and has a capacity $u_i$, which is the maximum demand that facility $i$ can serve. The cost of serving one unit demand of client $j$ in facility $i$ is $c_{ij}$. We want to open a subset of facilities and assign demand of clients to open facilities such that the demands of all the clients are met, no capacity constraint violated and the total cost of opening facilities and servicing clients is minimized. Service costs are nonnegative, symmetric, and satisfy the triangle inequality.Arora in [1, page 21] states that Arora, Raghavan and Rao [2] give a PTAS for the geometric case. They extend the algorithm to the capacitated case but the final solution may violate capacity constraints by small amount. What does he mean by small amount? I guess it means they give a PTAS that violates capacity constraints within factor $(1+\epsilon)$ for an arbitrary $\epsilon > 0$. Is this right?When I looked in [2], the only related result that I found was a $n^{O(\log^2 (n / \epsilon))}$ time algorithm for finding a $(1+\epsilon)$-approximate solution for the Capacitated $k$-median problem when we have uniform capacities. Does Arora refer to above result in [1]?[1] S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey. In Math. Programming, Ser. B, vol. 97, pp 43-69, 2003. [2] S. Arora, P. Raghavan, and S. Rao. Approximation schemes for the Euclideank-medians and related problems. In Proc. 30th ACM Symposium on Theoryof Computing, pp 106113, 1998.
Euclidean Capacitated Facility Location Problem
ds.algorithms;cg.comp geom;approximation algorithms