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 ε-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.