Algorithmic gap for Hochbaum's (greedy) algorithm for (metric) uncapacitated facility location

Question

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\left(\frac{\log n}{\log \log n}\right)$. 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 $\operatorname{cost}(i,A) = f_i + \sum{d_{ij}}$. The greedy algorithm is to choose the set $(i,A)$ that minimizes $\frac{\operatorname{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,\ldots,|\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\limits_{j=1}^ip^{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}^ip^{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}^ip^{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\left(\frac{\log n}{\log \log n}\right)$.

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.

---

_Reference

_{[1] Jain, K., Mahdian, M., Markakis, E. et al. (2003). Greedy Facility Location Algorithms Analyzed Using Dual Fitting with Factor-Revealing LP. Journal of the ACM. 50(6):795–824.}

Answer 1

I'm looking at the algorithm as it's described in Hochbaum (1982), which works like this: Suppose we have enumerated all $2^n-1$ subsets of the customers. Subset $P_m$ has cost $$C_m = \min_{j\in J} \left(\sum_{i\in P_m} c_{ij} + f_j\right),$$ i.e., the fixed plus transportation cost if we choose the best facility for the set $P_m$ of customers. At each iteration, we choose the $P_k$ that maximizes the ratio $$\frac{|P_m|}{C_m},$$ open the best facility for that $P_k$, remove the customers in $P_k$ from all of the other $P_m$ sets, and repeat.

I'm not exactly sure how that translates to the algorithm described in Jain et al. (2003); they say the two algorithms are equivalent, so let's take their word for it.

Their example has $k$ facilities with a fixed cost of $p^k$ for some $p$, all located at the same spot. (They don't give any restrictions on $p$ but the example only makes sense if $p$ is a positive integer.) There are $k-1$ groups of customers, called $S_1,\ldots,S_{k-1}$, oriented as rings around the facilities. $S_i$ contains $p^{k-i+1}$ customers, each at a distance of $\sum_{j=1}^i p^{j-1}$ from the facilities.

Consider the first iteration of Hochbaum's algorithm. Suppose $P_1=S_1$, $P_2=S_2$, and $P_{1,2}=S_1\cup S_2$. The relevant ratios are: $$\begin{align} \frac{|P_1|}{C_1} & = \frac{p^k}{p^k+p^kp^0} = \frac12 \\ \frac{|P_2|}{C_2} & = \frac{p^{k-1}}{p^k + p^{k-1}(p^0+p^1)} = \frac{1}{2p+1} < \frac12 \\ \frac{|P_{1,2}|}{C_{1,2}} & = \frac{p^k+p^{k-1}}{p^k + p^kp^0 + p^{k-1}(p^0+p^1)} = \frac{p+1}{3p+1} < \frac12. \end{align}$$ And presumably the pattern will repeat, in the sense that if we either add more "rings" to the subset, or we replace $S_1$ with a different "ring", the ratio will go down. Therefore, $P_1 = S_1$ attains the maximum ratio, so we open a facility (doesn't matter which one) and assign $S_1$ to it. Then remove $S_1$ from all of the other subsets, and repeat. The same logic will hold at the next iteration, so we will open a facility and assign $S_2$ to it, and so on. This continues until we have opened all $k$ facilities.