Totally $Δ$-modular IPs with two non-zeros in most rows
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910881437188096 |
|---|---|
| author | Kober, Stefan |
| author_facet | Kober, Stefan |
| contents | Integer programs (IPs) on constraint matrices with bounded subdeterminants are conjectured to be solvable in polynomial time. We give a strongly polynomial time algorithm to solve IPs where the constraint matrix has bounded subdeterminants and at most two non-zeros per row after removing a constant number of rows and columns. This result extends the work by Fiorini, Joret, Weltge \& Yuditsky (J. ACM 72(1), 1-50 (2025)) by allowing for additional, unifying constraints and variables. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_15282 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Totally $Δ$-modular IPs with two non-zeros in most rows Kober, Stefan Data Structures and Algorithms Discrete Mathematics Combinatorics Optimization and Control Integer programs (IPs) on constraint matrices with bounded subdeterminants are conjectured to be solvable in polynomial time. We give a strongly polynomial time algorithm to solve IPs where the constraint matrix has bounded subdeterminants and at most two non-zeros per row after removing a constant number of rows and columns. This result extends the work by Fiorini, Joret, Weltge \& Yuditsky (J. ACM 72(1), 1-50 (2025)) by allowing for additional, unifying constraints and variables. |
| title | Totally $Δ$-modular IPs with two non-zeros in most rows |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics Optimization and Control |
| url | https://arxiv.org/abs/2411.15282 |