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

Oliver Hinder

We analyze restarted PDHG on totally unimodular linear programs. In particular, we show that restarted PDHG finds an $\epsilon$-optimal solution in $O( H m_1^{2.5} \sqrt{\textbf{nnz}(A)}…