Publications

2022

1. Interior point methods are not worse than Simplex

   Xavier Allamigeon, Daniel Dadush, Georg Loho,  Bento Natura , and László A. Végh

   FOCS 2022 SIAM Journal on Computing Abstract arXiv Bib

   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.

   @inproceedings{N-ipm_not_worse_than_simplex,
     conference = {FOCS 2022},
     journal = {SIAM Journal on Computing},
     doi = {10.48550/ARXIV.2206.08810},
     author = {Allamigeon, Xavier and Dadush, Daniel and Loho, Georg and Natura, Bento 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 = {Interior point methods are not worse than Simplex},
     publisher = {arXiv},
     year = {2022},
     booktitle = {Annual Symposium on Foundations of Computer Science (FOCS)},
     note = {Invited to SIAM Journal on Computing (SICOMP) Special Issue},
     copyright = {Creative Commons Attribution 4.0 International}
   }

2. Circuit Imbalance Measures and Linear Programming

   Farbod Ekbatani,  Bento Natura , and László A. Végh

   Surveys in Combinatorics arXiv Bib

   @inbook{N-survey,
     journal = {Surveys in Combinatorics},
     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 2022},
     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.}
   }

3. On Circuit Diameter Bounds via Circuit Imbalances

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

   IPCO 2022 arXiv Bib

   @incollection{N-diameter,
     conference = {IPCO 2022},
     doi = {10.1007/978-3-031-06901-7_11},
     url = {https://doi.org/10.1007/978-3-031-06901-7_11},
     year = {2022},
     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)}
   }

4. A Faster Interior-Point Method for Sum-Of-Squares Optimization

   Shunhua Jiang,  Bento Natura , and Omri Weinstein

   ICALP 2022 Algorithmica arXiv Bib

   @inproceedings{jiang_et_al:LIPIcs.ICALP.2022.79,
     conference = {ICALP 2022},
     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 = {2022},
     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},
     annote = {Keywords: Interior Point Methods, Sum-of-squares Optimization, Dynamic Matrix Inverse}
   }

5. The Pareto cover problem

   Bento Natura , Meike Neuwohner, and Stefan Weltge

   ESA 2022 arXiv Bib

     conference = {ESA 2022},
     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},
     note = {In Annual European Symposium on Algorithms (ESA 2022)},
     copyright = {Creative Commons Attribution 4.0 International}
   }

2021

1. An Accelerated Newton-Dinkelbach Method and Its Application to Two Variables per Inequality Systems

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

   ESA 2021 Mathematics of Operations Research arXiv Bib

   @inproceedings{N-fraction-linear-programming,
     conference = {ESA 2021},
     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 = {2021},
     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},
     annote = {Keywords: Newton-Dinkelbach method, fractional optimization, parametric optimization, strongly polynomial algorithms, two variables per inequality systems, Markov decision processes, submodular function minimization}
   }

2020

1. A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix

   Daniel Dadush, Sophie Huiberts,  Bento Natura , and László A. Végh

   STOC 2020 Mathematical Programming Abstract arXiv Bib

   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,
     conference = {STOC 2020},
     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 = {2020},
     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}
   }

2. Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers

   Daniel Dadush,  Bento Natura , and László A. Végh

   FOCS 2020 arXiv Bib

   @inproceedings{N-revisit,
     conference = {FOCS 2020},
     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

1. Global Interconnect Optimization

   Siad Daboul, Stephan Held,  Bento Natura , and Daniel Rotter

   ICCAD 2019 ACM Transactions on Design Automation of Electronic Systems Bib

   @inproceedings{8942155,
     conference = {ICCAD 2019},
     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 = {2019},
     volume = {},
     number = {},
     pages = {1-8},
     doi = {10.1109/ICCAD45719.2019.8942155},
     journal = {ACM Transactions on Design Automation of Electronic Systems}
   }