Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.13493 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |