We consider the $k$-median problem on general metric spaces, subject to the condition that the instances are $\beta$-stable (i.e., the optimal solution using $k-1$ centers has a cost at least $(1+\beta)$ times that of the optimal solution with $k$ centers). We give a $(1.89+\epsilon)$-approximation algorithm for such i...
Rares-Darius Buhai, Vincent Cohen-Addad, Henry L. Fleischmann et al.· 1 citation
The Greedy algorithm of Jain, Mahdian, Markakis, Saberi, and Vazirani was the best Lagrangian-multiplier-preserving (LMP) approximation algorithm for facility location, and thus the engine behind the best $k$-median guarantees, for over two decades. Its $2$-LMP guarantee was only recently broken by a small amount ($(2-...
Rares-Darius Buhai, Vincent Cohen-Addad, Henry L. Fleischmann et al.· 0 citations
Recovering latent geometric structure from graph observations is a well-studied problem in statistical inference. Kapralov, Trevisan, and Wrzos-Kaminska (2026) introduced the problem of recovering the coordinate structure of the Boolean hypercube from a small random sample of its edges. More specifically, there are $n=...
