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

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{\mathbf{\text{nnz}}(A)}\log (H{m}_2\mathrm{/}\epsilon ))$ matrix-vector multiplies where $m_1$ is the number of constraints, $m_2$ the number of variables, $\mathbf{\text{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 $\epsilon$ is the distance to optimality of the outputted solution.