8 citations · 10 across the 11 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
math.OC2020
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…
cs.DS2020
Directed Shortest Paths via Approximate Cost Balancing
James B. Orlin, László A. Végh
We present an algorithm for all-pairs shortest paths computations in a directed graph with nodes, arcs, and nonnegative integer arc costs. This matches the complexi…
cs.DS2020
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…