<p>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. </p>

CC BY-SA 3.0
2012-03-05T03:47:00.463Z
Thats is indeed an interesting question. At the time it seemed that one can extend the Kolliopoulos and Rao paper to do this.
Sariel Har-Peled
CC BY-SA 3.0
2012-03-06T04:44:26.567Z
I was thinking the same for a while, but when I reread the proof of Theorem 4 of [Kolliopoulos-Rao-ESA'99] a few months ago, I found that you can not apply that theorem as a black box. The reason is that in the proof they assume that one can assign a client to any open facility while in the capacitated case you may violate the capacities with this modification. There may be a simple way around this, I haven't thought much about it.
randomizer
CC BY-SA 3.0
2012-03-02T22:07:25.520Z
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.
randomizer
CC BY-SA 3.0
2012-03-02T04:37:14.837Z
2012-03-02T04:37:14.837Z
Sariel Har-Peled
<p>In the <strong>Capacitated Facility Location Problem (CFLP)</strong>, 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.</p>

<p>Arora in [<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.4732&amp;rep=rep1&amp;type=pdf" rel="nofollow">1</a>, page 21] states that "Arora, Raghavan and Rao [<a href="http://www.cs.princeton.edu/~arora/pubs/facility.ps" rel="nofollow">2</a>] 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." <strong><em>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 &gt; 0$. Is this right?</em></strong></p>

<p>When I looked in [<a href="http://www.cs.princeton.edu/~arora/pubs/facility.ps" rel="nofollow">2</a>], 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. <strong><em>Does Arora refer to above result in [<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.4732&amp;rep=rep1&amp;type=pdf" rel="nofollow">1</a>]?</em></strong></p>

<p>[<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.4732&amp;rep=rep1&amp;type=pdf" rel="nofollow">1</a>] S. Arora. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.4732&amp;rep=rep1&amp;type=pdf" rel="nofollow">Approximation schemes for NP-hard geometric optimization problems: A survey.</a> In Math. Programming, Ser. B, vol. 97, pp 43-69, 2003. </p>

<p>[<a href="http://www.cs.princeton.edu/~arora/pubs/facility.ps" rel="nofollow">2</a>] S. Arora, P. Raghavan, and S. Rao. <a href="http://www.cs.princeton.edu/~arora/pubs/facility.ps" rel="nofollow">Approximation schemes for the Euclidean
k-medians and related problems.</a> In Proc. 30th ACM Symposium on Theory
of Computing, pp 106–113, 1998.</p>

<ds.algorithms><cg.comp-geom><approximation-algorithms>
Euclidean Capacitated Facility Location Problem
randomizer
# Euclidean Capacitated Facility Location Problem

(Asked by: username_0 on 2011-06-06)

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.4732&rep=rep1&type=pdf), page 21] states that "Arora, Raghavan and Rao [[2](http://www.cs.princeton.edu/~arora/pubs/facility.ps)] 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](http://www.cs.princeton.edu/~arora/pubs/facility.ps)], 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.4732&rep=rep1&type=pdf)]?***

[[1](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.4732&rep=rep1&type=pdf)] S. Arora. [Approximation schemes for NP-hard geometric optimization problems: A survey.](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.4732&rep=rep1&type=pdf) In Math. Programming, Ser. B, vol. 97, pp 43-69, 2003.

[[2](http://www.cs.princeton.edu/~arora/pubs/facility.ps)] S. Arora, P. Raghavan, and S. Rao. [Approximation schemes for the Euclidean
k-medians and related problems.](http://www.cs.princeton.edu/~arora/pubs/facility.ps) In Proc. 30th ACM Symposium on Theory
of Computing, pp 106–113, 1998.

**Tags:** ds.algorithms, cg.comp-geom, approximation-algorithms

---

## 1 answers

### Answer by username_1 on 2012-03-02. Score: 3

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: Thats is indeed an interesting question. At the time it seemed that one can extend the Kolliopoulos and Rao paper to do this.  
> **username_0**: I was thinking the same for a while, but when I reread the proof of Theorem 4 of [Kolliopoulos-Rao-ESA'99] a few months ago, I found that you can not apply that theorem as a black box. The reason is that in the proof they assume that one can assign a client to any open facility while in the capacitated case you may violate the capacities with this modification. There may be a simple way around this, I haven't thought much about it.  

---

