A Specialized Simplex Algorithm for Budget-Constrained Total Variation-Regularized Problems
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917508586405888 |
|---|---|
| author | Yang, Dominic |
| author_facet | Yang, Dominic |
| contents | We consider a class of linear programs on graphs with total variation regularization and a budgetary constraint. For these programs, we give a characterization of basic solutions in terms of rooted spanning forests with orientation on the underlying graph. This leads to an interpretation of the simplex method in terms of simple graph operations on these underlying forests. We exploit this structure to produce an accelerated simplex method and empirically show that such improvements can lead to an order of magnitude improvement in time when compared to state-of-the-art solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_13493 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Specialized Simplex Algorithm for Budget-Constrained Total Variation-Regularized Problems Yang, Dominic Optimization and Control We consider a class of linear programs on graphs with total variation regularization and a budgetary constraint. For these programs, we give a characterization of basic solutions in terms of rooted spanning forests with orientation on the underlying graph. This leads to an interpretation of the simplex method in terms of simple graph operations on these underlying forests. We exploit this structure to produce an accelerated simplex method and empirically show that such improvements can lead to an order of magnitude improvement in time when compared to state-of-the-art solvers. |
| title | A Specialized Simplex Algorithm for Budget-Constrained Total Variation-Regularized Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2507.13493 |