Publications
2025
- 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(n^{1.5}\log n)$ 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(2^{n} n^{1.5}\log(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}, journal_year = {2025}, doi = {10.1137/23M1554588}, url = {https://epubs.siam.org/doi/10.1137/23M1554588}, volume = {54}, number = {5}, pages = {S22--S178}, 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} }
2024
- On Circuit Diameter Bounds via Circuit Imbalances
We study the circuit diameter of polyhedra and establish that the circuit diameter of a system $\{x \in \mathbb{R}^n: Ax=b, 0 \le x \le u\}$ is bounded by $O(m \min\{m, n-m\} \log(m + \kappa_A) + n \log n)$, where $\kappa_A$ measures the circuit imbalance of the constraint matrix. This bound becomes strongly polynomial under certain conditions on matrix entries. Additionally, we develop circuit augmentation algorithms for linear programs using minimum-ratio circuit cancelling, solving LPs in $O(mn^2 \log(n + \kappa_A))$ augmentation steps.
@incollection{N-diameter, journal = {Mathematical Programming}, journal_year = {2024}, doi = {10.1007/978-3-031-06901-7_11}, url = {https://doi.org/10.1007/978-3-031-06901-7_11}, year = {2024}, publisher = {Springer International Publishing}, pages = {140--153}, author = {Dadush, Daniel and Koh, Zhuan Khye and Natura, Bento and Végh, László A.}, title = {On Circuit Diameter Bounds via Circuit Imbalances}, booktitle = {Integer Programming and Combinatorial Optimization (IPCO)} } - A strongly polynomial algorithm for linear programs with at most two non-zero entries per row or column
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, 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}, year = {2024}, }
2023
- A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix
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) $\mathrm{max} \\; c^\top x : Ax = b, x \geq 0, A \in \mathbb{R}^{m \times n}$, Vavasis and Ye developed a primal-dual interior point method using a _layered least squares_ (LLS) step, and showed that $O(n^{3.5} \log (\bar\chi_A+n))$ iterations suffice to solve (LP) exactly, where $\bar{\chi}_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 $\bar{\chi}^{\ast}_A$, defined as the minimum $\bar{\chi}_{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(m^2 n^2 + n^3)$ time algorithm which works on the linear matroid of $A$ to compute a nearly optimal diagonal rescaling $D$ satisfying $\bar{\chi}_{AD} \le n(\bar{\chi}^\ast)^3$. This algorithm also allows us to approximate the value of $\bar{\chi}_A$ up to a factor $n(\bar{\chi}^\ast)^2$. This result is in (surprising) contrast to that of Tunçel (Math. Prog. '99), who showed NP-hardness for approximating $\bar{\chi}_A$ to within $2^{\mathrm{poly}(\mathrm{rank}(A))}$. The key insight for our algorithm is to work with ratios $g_i/g_j$ of circuits of $A$ — i.e., minimal linear dependencies $Ag=0$ — which allow us to approximate the value of $\bar{\chi}_A^\ast$ 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(n^{2.5} \log(n) \log (\bar{\chi}^\ast_A+n))$ iteration bound for optimally solving (LP) using our algorithm. The same argument also yields a factor $n/\log n$ improvement on the iteration complexity bound of the original Vavasis-Ye algorithm.
@inproceedings{N-lls, 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}, year = {2023}, isbn = {9781450369794}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3357713.3384326}, doi = {10.1145/3357713.3384326}, booktitle = {Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing}, pages = {761–774}, numpages = {14}, keywords = {circuits, linear matroids, chi bar, interior point methods, Linear programming, condition number}, location = {Chicago, IL, USA}, series = {STOC 2020}, journal = {Mathematical Programming}, journal_year = {2023} } - A Faster Interior-Point Method for Sum-Of-Squares OptimizationShunhua Jiang, Bento Natura, and Omri Weinstein
We present an accelerated interior-point method for sum-of-squares polynomial optimization achieving $\tilde{O}(LU^{1.87})$ runtime, which represents polynomial improvement over existing semidefinite programming solvers. Our key contribution involves a dynamic data structure for maintaining the inverse of the Hessian of the SOS barrier function that handles multivariate cases by managing spectral approximations to low-rank perturbations of Hadamard products.
@inproceedings{jiang_et_al:LIPIcs.ICALP.2022.79, author = {Jiang, Shunhua and Natura, Bento and Weinstein, Omri}, title = {A Faster Interior-Point Method for Sum-Of-Squares Optimization}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP)}, pages = {79:1--79:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, isbn = {978-3-95977-235-8}, issn = {1868-8969}, year = {2023}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, url = {https://drops.dagstuhl.de/opus/volltexte/2022/16420}, urn = {urn:nbn:de:0030-drops-164205}, doi = {10.4230/LIPIcs.ICALP.2022.79}, journal = {Algorithmica}, journal_year = {2023}, annote = {Keywords: Interior Point Methods, Sum-of-squares Optimization, Dynamic Matrix Inverse} } - 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. Our core contribution involves a new buffered routing subroutine that computes optimized routes based on Lagrangean resource prices. Our algorithm achieves practical efficiency, demonstrating improvements in timing while reducing netlength and power consumption on 7nm microprocessor designs.
@inproceedings{8942155, author = {Daboul, Siad and Held, Stephan and Natura, Bento and Rotter, Daniel}, booktitle = {2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)}, title = {Global Interconnect Optimization}, year = {2023}, volume = {}, number = {}, pages = {1-8}, doi = {10.1109/ICCAD45719.2019.8942155}, journal = {ACM Transactions on Design Automation of Electronic Systems}, journal_year = {2023} }
2022
- 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. We use the Bregman divergence as a potential function combined with combinatorial arguments to achieve improved convergence bounds. For linear fractional optimization, we improve the convergence to $O(m \log m)$ iterations from $O(m^2 \log m)$. For two-variable inequality systems, we obtain a strongly polynomial label-correcting algorithm running in $O(mn)$ iterations, with specialized $O(m + n \log n)$ performance for Markov Decision Processes. We also provide a simplified variant of parametric submodular function minimization.
@inproceedings{N-fraction-linear-programming, 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}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {36:1--36:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, isbn = {978-3-95977-204-4}, issn = {1868-8969}, year = {2022}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, url = {https://drops.dagstuhl.de/opus/volltexte/2021/14617}, urn = {urn:nbn:de:0030-drops-146172}, doi = {10.4230/LIPIcs.ESA.2021.36}, journal = {Mathematics of Operations Research}, journal_year = {2022}, annote = {Keywords: Newton-Dinkelbach method, fractional optimization, parametric optimization, strongly polynomial algorithms, two variables per inequality systems, Markov decision processes, submodular function minimization} } - 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, journal = {Surveys in Combinatorics}, journal_year = {2022}, place = {Cambridge}, series = {London Mathematical Society Lecture Note Series}, title = {Circuit Imbalance Measures and Linear Programming}, doi = {10.1017/9781009093927.004}, 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} }
2020
- 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 \bar\chi_A$ suffices to solve any LP exactly. By incorporating van den Brand's recent algorithm, we achieve $O(mn^{\omega+1} \log(n)\log(\bar\chi_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} }