Settling the Approximability of Submodular Facility Location

In submodular facility location (SFL), introduced by Svitkina and Tardos (SODA 2006), clients $\mathcal{C}$ in a metric space are assigned to facilities $\mathcal{F}$. A facility serving a set $S\subseteq \mathcal{C}$ of clients incurs cost $g(S)$, where $g$ is a monotone submodular function common to all facilities. The best known approximation factor for SFL is $O(\log \log \mathrm{\mid }\mathcal{C}\mathcal{\mid })$, due to Abbasi, Adamczyk, Bosch-Calvo, Byrka, Grandoni, Sornat, and Tinguely (ICALP 2024), improving on the $O(\log \mathrm{\mid }\mathcal{C}\mathcal{\mid })$-approximation of Svitkina and Tardos. We show that this is best possible up to a constant factor in the value-oracle model by showing that there exists no algorithm with only polynomially many queries to $g$ with approximation ratio $o(\log \log \mathrm{\mid }\mathcal{C}\mathcal{\mid })$. This bound holds for algorithms with unlimited computation time, and when $g$ is restricted to matroid rank functions. We also show that the natural linear programming relaxation has an integrality gap of $\mathrm{\Theta }(\log \log \mathrm{\mid }\mathcal{C}\mathcal{\mid })$. Our lower bound follows by constructing an extension of Vondrák’s symmetry-gap approach (FOCS 2009) for matroid rank functions.