2026
- Circuit Diameter of Polyhedra is Strongly PolynomialBento 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 circuit diameter of a polyhedron P={x∈Rn:Ax=b,x≥0} with A∈Rm×n is O(m2logm). Our construction yields monotone circuit walks, giving the same bound for the monotone circuit diameter.
The circuit diameter, introduced by Borgwardt, Finhold, and Hemmecke (SIDMA 2015), is a natural relaxation of the combinatorial diameter that allows steps along circuit directions rather than only along edges. All prior upper bounds on the circuit diameter were only weakly polynomial. Finding a circuit augmentation algorithm that matches this bound would yield a strongly polynomial time algorithm for linear programming, resolving Smale's 9th problem.@inproceedings{natura2026circuitdiameterpolyhedrastrongly, author = {Natura, Bento}, title = {Circuit Diameter of Polyhedra is Strongly Polynomial}, year = {2026}, eprint = {2602.06958}, archiveprefix = {arXiv}, primaryclass = {math.OC}, } - Trust Region Interior Point Methods: Optimal ℓ2- and Faster Wide-Neighborhood Path FollowingDaniel Dadush, Haoyuan Ma, Bento Natura, and László A. Végh
We present improved running time and iteration complexities of interior point methods for linear programs parametrized by the straight line complexity, i.e., the minimum number of segments of any piecewise linear curve traversing a particular neighborhood of the central path. While the standard measure of progress is the reduction in duality gap, the straight line complexity provides a stronger instance-wise bound, reflecting the combinatorial structure of the problem.
Our first main result is a wide neighborhood interior point method whose running time is the wide-neighborhood straight line complexity times current matrix multiplication time, improving in essence a factor n over the algorithm by Allamigeon, Dadush, Loho, Natura, and Végh (SIAM J. Comput. 2025). The algorithm can be seen as a boosted version of the robust interior point methods of Cohen, Lee and Song (JACM 2021) and van den Brand (SODA 2020) that can reduce the gap by a polynomial factor in current matrix multiplication time. Our algorithm is also able to traverse any near-linear segments of the central path in current matrix multiplication time, independently of the length of the segment.
Our second main result focuses on interior point methods that stay in the narrow ℓ2-neighborhood. We give a much stronger analysis of the ℓ2-trust region interior point method introduced by Lan, Monteiro and Tsuchiya (SIAM J. Optim. 2009), showing that it is approximately instance optimal in this neighborhood: the number of iterations is within a constant factor of the lower bound.
A main ingredient in both methods are trust region subroutines with ℓ∞ and ℓ2-constraints, respectively. We develop fast and strongly polynomial algorithms for solving both these problems to high accuracy. In the ℓ2-setting, this answers an open question by Lan, Monteiro and Tsuchiya.@inproceedings{trust-region-ipm, booktitle = {Proceedings of the 58th Annual ACM SIGACT Symposium on Theory of Computing (STOC)}, author = {Dadush, Daniel and Ma, Haoyuan and Natura, Bento and Végh, László A.}, title = {Trust Region Interior Point Methods: Optimal $\ell_2$- and Faster Wide-Neighborhood Path Following}, pages = {755--766}, publisher = {ACM}, year = {2026}, doi = {10.1145/3798129.3800790}, url = {https://doi.org/10.1145/3798129.3800790} }
2024
- A Strongly Polynomial Algorithm for Linear Programs with at Most Two Non-Zero Entries per Row or ColumnFull versions: Part I (initialization & bit complexity) on arXiv; Part II (straight line complexity bound) in preparation.
We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Primal and dual feasibility were shown by Megiddo (SICOMP '83) and Végh (MOR '17) respectively. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale's 9th problem. Our approach is based on the recent primal-dual interior point method (IPM) due to Allamigeon, Dadush, Loho, Natura and Végh (FOCS '22). The number of iterations needed by the IPM is bounded, up to a polynomial factor in the number of inequalities, by the straight line complexity of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By applying a reduction of Hochbaum (ORL '04), the same bound applies to any linear program with at most two non-zeros per column or per row. To be able to run the IPM, one requires a suitable initial point. For this purpose, we develop a novel multistage approach, where each stage can be solved in strongly polynomial time given the result of the previous stage. Beyond this, substantial work is needed to ensure that the bit complexity of each iterate remains bounded during the execution of the algorithm. For this purpose, we show that one can maintain a representation of the iterates as a low complexity convex combination of vertices. Our approach is black-box and can be applied to any log-barrier path following method.
@inproceedings{min-cost-gen-flow, year = {2024}, doi = {10.1145/3618260.3649764}, booktitle = {Proceedings of the 56th Annual ACM SIGACT Symposium on Theory of Computing (STOC)}, author = {Dadush, Daniel and Koh, Zhuan Khye and Natura, Bento and Olver, Neil and Végh, László A.}, keywords = {Optimization and Control (math.OC), Data Structures and Algorithms (cs.DS), FOS: Mathematics, FOS: Mathematics, FOS: Computer and information sciences, FOS: Computer and information sciences}, title = {A Strongly Polynomial Algorithm for Linear Programs with at Most Two Non-Zero Entries per Row or Column}, }
2022
- Interior Point Methods Are Not Worse than Simplex
We develop a new interior point method for solving linear programs. Our algorithm is universal in the sense that it matches the number of iterations of any interior point method that uses a self-concordant barrier function up to a factor O(n1.5logn) for an n-variable linear program in standard form.
The running time bounds of interior point methods depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. Our algorithm also admits a combinatorial upper bound, terminating with an exact solution in O(2nn1.5log(n)) iterations. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations.@article{N-ipm_not_worse_than_simplex, journal = {SIAM Journal on Computing}, doi = {10.1137/23M1554588}, url = {https://epubs.siam.org/doi/10.1137/23M1554588}, volume = {54}, number = {5}, pages = {FOCS22-178--FOCS22-264}, author = {Allamigeon, Xavier and Dadush, Daniel and Loho, Georg and Natura, Bento and Végh, László A.}, title = {Interior Point Methods Are Not Worse than Simplex}, publisher = {SIAM}, year = {2025} } - On Circuit Diameter Bounds via Circuit Imbalances
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 diameter of a system {x∈Rn:Ax=b,0≤x≤u} for A∈Rm×n is bounded by O(mmin{m,n−m}log(m+κA)+nlogn), where κA is the circuit imbalance measure of the constraint matrix. This yields a strongly polynomial circuit diameter bound if e.g., all entries of A have polynomially bounded encoding length in n. Further, we present circuit augmentation algorithms for LPs using the minimum-ratio circuit cancelling rule. Even though the standard minimum-ratio circuit cancelling algorithm is not finite in general, our variant can solve an LP in O(mn2log(n+κA)) augmentation steps.
@article{N-diameter, journal = {Mathematical Programming}, author = {Dadush, Daniel and Koh, Zhuan Khye and Natura, Bento and Végh, László A.}, title = {On Circuit Diameter Bounds via Circuit Imbalances}, volume = {206}, number = {1--2}, pages = {631--662}, year = {2024}, publisher = {Springer}, doi = {10.1007/s10107-024-02107-x}, url = {https://doi.org/10.1007/s10107-024-02107-x} } - A Faster Interior-Point Method for Sum-of-Squares OptimizationShunhua Jiang, Bento Natura, and 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 Lasserre hierarchy. Let p=∑iqi2 be an n-variate SOS polynomial of degree 2d. Denoting by L:=(dn+d) and U:=(2dn+2d) the dimensions of the vector spaces in which qi's and p live respectively, our algorithm runs in time O~(LU1.87). This is polynomially faster than state-of-art SOS and semidefinite programming solvers, which achieve runtime O~(L0.5min{U2.37,L4.24}). The centerpiece of our algorithm is a dynamic data structure for maintaining the inverse of the Hessian of the SOS barrier function under the polynomial interpolant basis, which efficiently extends to multivariate SOS optimization, and requires maintaining spectral approximations to low-rank perturbations of elementwise (Hadamard) products. This is the main challenge and departure from recent IPM breakthroughs using inverse-maintenance, where low-rank updates to the slack matrix readily imply the same for the Hessian matrix.
@article{jiang_et_al:LIPIcs.ICALP.2022.79, journal = {Algorithmica}, author = {Jiang, Shunhua and Natura, Bento and Weinstein, Omri}, title = {A Faster Interior-Point Method for Sum-of-Squares Optimization}, volume = {85}, number = {9}, pages = {2843--2884}, year = {2023}, publisher = {Springer}, doi = {10.1007/s00453-023-01112-4}, url = {https://doi.org/10.1007/s00453-023-01112-4} } - Circuit Imbalance Measures and Linear ProgrammingFarbod Ekbatani, Bento Natura, and 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-minimal nonzero vectors of the space. The fractional circuit imbalance measure functions as a key parameter in linear programming, while two integer variants help characterize polyhedra integrality properties. We survey both classical and recent applications, including linear programming algorithms dependent on constraint matrices and circuit augmentation methods. Additionally, we establish novel bounds on polyhedra diameter using the fractional circuit imbalance measure.
@inbook{N-survey, doi = {10.1017/9781009093927.004}, journal = {Surveys in Combinatorics}, place = {Cambridge}, series = {London Mathematical Society Lecture Note Series}, title = {Circuit Imbalance Measures and Linear Programming}, booktitle = {Surveys in Combinatorics}, publisher = {Cambridge University Press}, year = {2022}, pages = {64–114}, collection = {London Mathematical Society Lecture Note Series}, author = {Ekbatani, Farbod and Natura, Bento and Végh, László A.} } - The Pareto Cover ProblemBento Natura, Meike Neuwohner, and Stefan Weltge
We introduce an optimization problem focused on selecting k points in [0,1]n to minimize the expected cost of the cheapest point that dominates a random point from [0,1]n. We demonstrate the problem is NP-hard for k=2 with binary coordinates, while providing an FPTAS (fully polynomial-time approximation scheme) for fixed k under reasonable distributional assumptions. The work has applications where predefined products with specific feature subsets fulfill customer requests.
@inproceedings{pareto-cover, booktitle = {30th Annual European Symposium on Algorithms (ESA)}, doi = {10.48550/ARXIV.2202.08035}, author = {Natura, Bento and Neuwohner, Meike and Weltge, Stefan}, keywords = {Optimization and Control (math.OC), Computational Geometry (cs.CG), Discrete Mathematics (cs.DM), Data Structures and Algorithms (cs.DS), FOS: Mathematics, FOS: Mathematics, FOS: Computer and information sciences, FOS: Computer and information sciences}, title = {The Pareto Cover Problem}, publisher = {arXiv}, year = {2022}, copyright = {Creative Commons Attribution 4.0 International} }
2021
- An Accelerated Newton-Dinkelbach Method and Its Application to Two Variables per Inequality Systems
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 acceleration halves the Bregman divergence between the current iterate and the optimal solution within every two iterations. Using the Bregman divergence as a potential in conjunction with combinatorial arguments, we obtain strongly polynomial algorithms in three applications domains: (i) For linear fractional combinatorial optimization, we show a convergence bound of O(mlogm) iterations; the previous best bound was O(m2logm) by Wang et al. (2006). (ii) We obtain a strongly polynomial label-correcting algorithm for solving linear feasibility systems with two variables per inequality (2VPI). For a 2VPI system with n variables and m constraints, our algorithm runs in O(mn) iterations. Every iteration takes O(mn) time for general 2VPI systems, and O(m+nlogn) time for the special case of deterministic Markov Decision Processes (DMDPs). This extends and strengthens a previous result by Madani (2002) that showed a weakly polynomial bound for a variant of the Newton-Dinkelbach method for solving DMDPs. (iii) We give a simplified variant of the parametric submodular function minimization result by Goemans et al. (2017).
@article{N-fraction-linear-programming, journal = {Mathematics of Operations Research}, author = {Dadush, Daniel and Koh, Zhuan Khye and Natura, Bento and Végh, László A.}, title = {An Accelerated Newton-Dinkelbach Method and Its Application to Two Variables per Inequality Systems}, volume = {48}, number = {4}, pages = {1934--1958}, year = {2023}, publisher = {INFORMS}, doi = {10.1287/moor.2022.1326}, url = {https://doi.org/10.1287/moor.2022.1326} }
2020
- A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix
Dodu Prize 2020, awarded to Bento Natura for the talk presenting this work.
Following the breakthrough work of Tardos (Oper. Res. '86) in the bit-complexity model, Vavasis and Ye (Math. Prog. '96) gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear program (LP) maxc⊤x:Ax=b,x≥0,A∈Rm×n, Vavasis and Ye developed a primal-dual interior point method using a layered least squares (LLS) step, and showed that O(n3.5log(χˉA+n)) iterations suffice to solve (LP) exactly, where χˉA is a condition measure controlling the size of solutions to linear systems related to A. Monteiro and Tsuchiya (SIAM J. Optim. '03), noting that the central path is invariant under rescalings of the columns of A and c, asked whether there exists an LP algorithm depending instead on the measure χˉA∗, defined as the minimum χˉAD value achievable by a column rescaling AD of A, and gave strong evidence that this should be the case. We resolve this open question affirmatively. Our first main contribution is an O(m2n2+n3) time algorithm which works on the linear matroid of A to compute a nearly optimal diagonal rescaling D satisfying χˉAD≤n(χˉ∗)3. This algorithm also allows us to approximate the value of χˉA up to a factor n(χˉ∗)2. This result is in (surprising) contrast to that of Tunçel (Math. Prog. '99), who showed NP-hardness for approximating χˉA to within 2poly(rank(A)). The key insight for our algorithm is to work with ratios gi/gj of circuits of A — i.e., minimal linear dependencies Ag=0 — which allow us to approximate the value of χˉA∗ by a maximum geometric mean cycle computation in what we call the circuit ratio digraph of A. While this resolves Monteiro and Tsuchiya's question by appropriate preprocessing, it falls short of providing either a truly scaling invariant algorithm or an improvement upon the base LLS analysis. In this vein, as our second main contribution we develop a scaling invariant LLS algorithm, which uses and dynamically maintains improving estimates of the circuit ratio digraph, together with a refined potential function based analysis for LLS algorithms in general. With this analysis, we derive an improved O(n2.5log(n)log(χˉA∗+n)) iteration bound for optimally solving (LP) using our algorithm. The same argument also yields a factor n/logn improvement on the iteration complexity bound of the original Vavasis-Ye algorithm.
@article{N-lls, journal = {Mathematical Programming}, author = {Dadush, Daniel and Huiberts, Sophie and Natura, Bento and Végh, László A.}, title = {A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix}, volume = {204}, number = {1--2}, pages = {135--206}, year = {2023}, publisher = {Springer}, doi = {10.1007/s10107-023-01956-2}, url = {https://doi.org/10.1007/s10107-023-01956-2} } - Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate SolversDaniel Dadush, Bento Natura, and László A. Végh
We extend Tardos's framework for linear programming by replacing exact LP solves with approximate ones. We demonstrate that inverse polynomial accuracy in n and logχˉA suffices to solve any LP exactly. By incorporating van den Brand's recent algorithm, we achieve O(mnω+1log(n)log(χˉA+n)) arithmetic operations, surpassing the Vavasis-Ye interior point method. Our approach combines approximate LP solutions using constructive proximity theorems to maintain low accuracy requirements while computing exact primal and dual solutions.
@inproceedings{N-revisit, author = {Dadush, Daniel and Natura, Bento and Végh, László A.}, title = {Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers}, booktitle = {61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020}, pages = {931--942}, publisher = {IEEE}, year = {2020}, url = {https://doi.org/10.1109/FOCS46700.2020.00091}, doi = {10.1109/FOCS46700.2020.00091}, timestamp = {Fri, 09 Apr 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/focs/DadushNV20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
2019
- Global Interconnect OptimizationSiad Daboul, Stephan Held, Bento Natura, and Daniel Rotter
We propose a new comprehensive solution to global interconnect optimization. Traditional buffering algorithms mostly insert repeaters on a net-by-net basis based on slacks and possibly guided by global wires.
We show how to integrate routing congestion, placement congestion, global timing constraints, power consumption, and additional constraints into a single resource sharing formulation. The core of our algorithm is a new buffered routing subroutine. Given a net and Lagrangean resource prices for routing, timing, placement, and power, it computes a buffered Steiner tree. The resource sharing framework provides a special multiplicative price update for fast convergence.
Our algorithm is fast enough for practical instances. We demonstrate experimentally on 7nm microprocessor units that it significantly improves timing while reducing netlength and power consumption in an industrial design flow. Our implementation scales well under parallelization with up to 128 threads.@article{8942155, journal = {ACM Transactions on Design Automation of Electronic Systems}, author = {Daboul, Siad and Held, Stephan and Natura, Bento and Rotter, Daniel}, title = {Global Interconnect Optimization}, volume = {28}, number = {5}, pages = {1--24}, year = {2023}, publisher = {Association for Computing Machinery}, doi = {10.1145/3587044}, url = {https://doi.org/10.1145/3587044} }
Thesis
- Exact Linear Programming: Circuits, Curvature, and DiameterBento NaturaLondon School of Economics and Political Science, 2022
- Richard Rado Prize 2024, German Mathematical Society (DMV): biennial prize for the best dissertation in Discrete Mathematics.
- Doctoral Award 2023, runner-up, The Operational Research Society (UK).
- PhD Prize 2023, Department of Mathematics, London School of Economics.
We study Linear Programming (LP) and present novel algorithms. In particular, we study LP in the context of circuits, which are support-minimal vectors of linear spaces. Our results will be stated in terms of the circuit imbalance (CI), which is the worst-case ratio of nonzero entries of circuits and whose properties we study in detail. We present following results with logarithmic dependency on CI. (i) A scaling-invariant Interior-Point Method, which solves LP in time that is polynomial in the dimensions, answering an open question by Monteiro-Tsuchiya in the affirmative. This closes a long line of work by Vavasis-Ye and Monteiro-Tsuchiya; (ii) We introduce a new polynomial-time path-following interior point method where the number of iterations admits a singly exponential upper bound. This complements recent results, that path-following method must take at least exponentially many iterations; (iii) We further provide similar upper bounds on a natural notion of curvature of the central path; (iv) A black-box algorithm that requires only quadratically many calls to an approximate LP solver to solve LP exactly. This significantly strengthens the framework by Tardos, which requires exact solvers and whose runtime is logarithmic in the maximum subdeterminant of the constraint matrix. The maximum subdeterminant is exponentially bigger than CI, already for fundamental combinatorial problems such as matchings; (v) Furthermore, we obtain a circuit diameter that is quadratic in the number of variables, giving the first polynomial bound for general LP where CI is exponential. Unlike in the simplex method, one does not have to augment around the edges of the polyhedron: Augmentations can be in any circuit direction; (vi) Lastly, we present an accelerated version of the Newton–Dinkelbach method, which extends the black-box framework to certain classes of fractional and parametric optimization problems. Using the Bregman divergence as a potential in conjunction with combinatorial arguments, we obtain improved runtimes over the non-accelerated version.
@phdthesis{natura2022thesis, author = {Natura, Bento}, title = {Exact Linear Programming: Circuits, Curvature, and Diameter}, school = {London School of Economics and Political Science}, year = {2022}, }