Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2309.03988 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
Table des matières:
- We analyze restarted PDHG on totally unimodular linear programs. In particular, we show that restarted PDHG finds an $ε$-optimal solution in $O( H m_1^{2.5} \sqrt{\textbf{nnz}(A)} \log(H m_2 /ε) )$ matrix-vector multiplies where $m_1$ is the number of constraints, $m_2$ the number of variables, $\textbf{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.