10 papers
Settling the Approximability of Submodular Facility Location
Adam N. Elmachtoub, Bento Natura, Meike Neuwohner
In submodular facility location (SFL), introduced by Svitkina and Tardos (SODA 2006), clients in a metric space are assigned to facilities . A facility serving a s…
Circuit Diameter of Polyhedra is Strongly Polynomial
Bento Natura
We prove a strongly polynomial bound on the circuit diameter of polyhedra, resolving the circuit analogue of the polynomial Hirsch conjecture. Specifically, we show that the circui…
Interior point methods are not worse than Simplex
Xavier Allamigeon, Daniel Dadush, Georg Loho +2
We develop a new `subspace layered least squares' interior point method (IPM) for solving linear programs. Applied to an -variable linear program in standard form, the iteration…
A Faster Interior-Point Method for Sum-of-Squares Optimization
Shunhua Jiang, Bento Natura, Omri Weinstein
We present a faster interior-point method for optimizing sum-of-squares (SOS) polynomials, which are a central tool in polynomial optimization and capture convex programming in the…
The Pareto cover problem
Bento Natura, Meike Neuwohner, Stefan Weltge
We introduce the problem of finding a set of points in such that the expected cost of the cheapest point in that dominates a random point from is mi…
On Circuit Diameter Bounds via Circuit Imbalances
Daniel Dadush, Zhuan Khye Koh, Bento Natura +1
We study the circuit diameter of polyhedra, introduced by Borgwardt, Finhold, and Hemmecke (SIDMA 2015) as a relaxation of the combinatorial diameter. We show that the circuit diam…
Circuit imbalance measures and linear programming
Farbod Ekbatani, Bento Natura, László A. Végh
We study properties and applications of various circuit imbalance measures associated with linear spaces. These measures describe possible ratios between nonzero entries of support…
Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers
Daniel Dadush, Bento Natura, László A. Végh
In breakthrough work, Tardos (Oper. Res. '86) gave a proximity based framework for solving linear programming (LP) in time depending only on the constraint matrix in the bit comple…
An Accelerated Newton-Dinkelbach Method and its Application to Two Variables Per Inequality Systems
Daniel Dadush, Zhuan Khye Koh, Bento Natura +1
We present an accelerated, or 'look-ahead' version of the Newton-Dinkelbach method, a well-known technique for solving fractional and parametric optimization problems. This acceler…
A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
Daniel Dadush, Sophie Huiberts, Bento Natura +1
Following the breakthrough work of Tardos in the bit-complexity model, Vavasis and Ye gave the first exact algorithm for linear programming in the real model of computation with ru…