Settling the Approximability of Submodular Facility Location

Abstract

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 |\mathcal{C}|)$, due to Abbasi, Adamczyk, Bosch-Calvo, Byrka, Grandoni, Sornat, and Tinguely (ICALP 2024), improving on the $O(\log |\mathcal{C}|)$-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 |\mathcal{C}|)$. 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 $\Theta (\log \log |\mathcal{C}|)$. Our lower bound follows by constructing an extension of Vondrák's symmetry-gap approach (FOCS 2009) for matroid rank functions.

arXiv commentAn initial proof of a constant-factor lower bound was obtained using ChatGPT 6.1 Astra. The stronger result shown in the paper was obtained in conversations with Claude Opus 5.5 and ChatGPT 6.1 Astra. The authors have improved the presentation and simplified the arguments. 25 pages, 2 figures