Preprints

2026

1. Settling the Approximability of Submodular Facility Location 

   Adam N. Elmachtoub, Bento Natura, and Meike Neuwohner

   Preprint

   arXiv Scholar Cite

   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.

   Copy

   @misc{elmachtoub2026submodularfacilitylocation,
     author = {Elmachtoub, Adam N. and Natura, Bento and Neuwohner, Meike},
     title = {Settling the Approximability of Submodular Facility Location},
     year = {2026},
     eprint = {2610.18828},
     archiveprefix = {arXiv},
     primaryclass = {cs.DS},
   }

2. Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time 

   Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, and László A. Végh

   Full version of the initialization and bit-complexity part of our STOC 2024 paper.

   Preprint

   arXiv Cite

   Recently, Allamigeon, Dadush, Loho, Natura, and Végh (ADLNV, SICOMP 2025) introduced an interior point method for linear programs whose number of iterations is bounded by the so-called straight line complexity (SLC) of the instance. This yields a strongly polynomial bound on the number of iterations of the corresponding interior point algorithm for broad classes of linear programs. In particular, in the companion paper we give a strongly polynomial straight line complexity bound for two-variable-per-inequality linear programs. However, in order to obtain a strongly polynomial algorithm for these classes, one also needs to address two important technical issues: initialization and bit-complexity bounds. Standard IPM initialization techniques either require numerical estimates that cannot be obtained in the strongly polynomial model, or involve modifying the instance in ways that do not preserve the geometry of the original LP, potentially affecting the SLC.
   In this work, we present an initialization framework for interior point methods for linear programming, along with a rounding procedure that ensures the continued feasibility of the IPM. We develop a multistage scheme in which each stage can be initialized in strongly polynomial time given the output of the previous stage. Additionally, we address the challenge of controlling the bit complexity of each iterate throughout the algorithm. To this end, we show that it is possible to represent iterates as low-complexity convex combinations of vertices and extreme rays. Our combinatorial rounding step is independent of the algorithm in ADLNV 2025, and can be applied more broadly in the context of path-following methods.

   Copy

   @misc{dadush2026slcstronglypolynomialtime,
     author = {Dadush, Daniel and Koh, Zhuan Khye and Natura, Bento and Olver, Neil and Végh, László A.},
     title = {Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time},
     year = {2026},
     eprint = {2610.26073},
     archiveprefix = {arXiv},
     primaryclass = {math.OC},
   }