4 papers
Empirical Asymptotic Runtime Analysis of Linear Programming Algorithms
Edward Rothberg
This paper takes an empirical look at asymptotic runtime growth rates for the most widely used algorithms for solving linear programming (LP) problems across a set of six optimizat…
Hybridizing PDHG and Interior-Point Methods
Edward Rothberg
The Primal-Dual Hybrid Gradient (PDHG) algorithm is a first-order method that can exploit GPUs to solve large-scale linear programming problems. The approach can often be faster th…
Backing PDHG into a Corner
Edward Rothberg
Recent enhancements to the Primal-Dual Hybrid Gradient (PDHG) algorithm have enabled GPUs to efficiently solve large linear programming problems, often faster than the long-dominan…
Concurrent Crossover for PDHG
Edward Rothberg
First-order methods based on the PDHG algorithm have recently emerged as a viable option for efficiently solving large-scale linear programming problems. One highly desirable prope…