9
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Randomizer
    Mar 2, 2012 at 22:07
  • $\begingroup$ Thats is indeed an interesting question. At the time it seemed that one can extend the Kolliopoulos and Rao paper to do this. $\endgroup$
    – Sariel Har-Peled
    Mar 5, 2012 at 3:47
  • $\begingroup$ 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. $\endgroup$
    – Randomizer
    Mar 6, 2012 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.