0
$\begingroup$

In Jain et. al (2003), at the bottom of page 801, they construct an instance of (metric) uncapacitated facility location for which they claim the greedy (Hochbaum's) algorithm has gap $\Omega(\frac{\log n}{\log \log n})$. The algorithm is as follows:

Construct an instance of set cover, where the ground set of elements is the set of clients $D$ and the set system contains all sets of the form $(i,A)$ where $i \in F$ is a facility and $A \subseteq D$ is a set of clients. Set $(i,A)$ covers the elements in $A$ and $cost(i,A) = f_i + \sum{d_{ij}}$. The greedy algorithm is to choose the set $(i,A)$ that minimizes $\frac{cost(i,A)}{|A \cap \text{Uncovered}|}$. This can be done in polytime by iterating through the facilities $i \in F$ and through $s = 1...|\text{Uncovered}|$ and considering $A$ to be the $s$ closest uncovered clients to facility $i$.

Part of the proof of Jain et. al is to claim that (on the instance they construct) the above greedy algorithm will open all $k$ facilities, while the optimal thing to do is to open only one of the facilities. I can't seem to see why the greedy algorithm will open all facilities. I can see how this would be the case if the cost of each element in set $S_i$ is $\sum_{j=1...i}p^{j-1}$, but in this case opening one facility will have cost $p^k + \sum_{i=1...k-1}p^{k-i+1}\sum_{j=1...i}p^{j-1} = \Theta(kp^k)$, while they claim that the optimal cost (that of opening one facility) is $p^k + \sum_{i=1...k-1}\sum_{j=1...i}p^{j-1} = \Theta(p^k)$. A central part of their proof seems to be that since the greedy algorithm described above will open all $k$ facilities, it will have cost $\Omega(kp^k)$ and therefore, the gap between the algorithms performance and the optimum is $\Omega(k)$. Since there are $n = \Theta(p^k)$ clients, $k = \log_p n = \ln n/\ln p$, and therefore for $p = \ln n$, we have that the gap is $\Omega(\frac{\log n}{\log \log n})$. Another question I have is that for $p = O(1)$, wouldn't this result in a gap of $\Omega(\log n)$ which is a stronger result? Why doesn't this work? The last sentence of their paragraph is "We do not know whether the approximation factor of Hochbaum’s algorithm on metric instances is strictly less than $\log n$." So I assume I'm missing something.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.