Euclidean Capacitated Facility Location Problem

In the Capacitated Facility Location Problem (CFLP), we are given a set 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 Euclidean k-medians and related problems. In Proc. 30th ACM Symposium on Theory of Computing, pp 106–113, 1998.

If I rmemeber correctly, you have to approximate the number of clients connected to each gate. Otherwise, you would immediately get something like $O(n^{O(g)})$, where $g$ is the number of gates in a subproblem. By approximating this number up to a facotr of $(1+\varepsilon/\log n)$ throughout the dynamic programming one can get a $(1+\varepsilon)$ error in the end. That would yield running times similar to what you stated above.
• If I get it right, you mean that their algorithm extends to a QPTAS with $(1+\epsilon)$ violation of capacities for the uniform capacitated facility location problem. I wonder if there is a PTAS with $(1+\epsilon)$ violation for this problem. Mar 2 '12 at 22:07