# Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs

arXiv: https://arxiv.org/abs/2309.03988 · HTML: https://mlsanity.com/paper/2309.03988/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2023.

## Built on by (most cited first, 1 of 1)

- [PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming](https://mlsanity.com/paper/2406.01908/) (2024)

## Abstract (arXiv)

We analyze restarted PDHG on totally unimodular linear programs. In particular, we show that restarted PDHG finds an ε-optimal solution in O( H m12.5 √nnz(A) log(H m2 /ε) ) matrix-vector multiplies where m1 is the number of constraints, m2 the number of variables, nnz(A) is the number of nonzeros in the constraint matrix, H is the largest absolute coefficient in the right hand side or objective vector, and ε is the distance to optimality of the outputted solution.