Circuit and Graver Walks and Linear and Integer Programming
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_ | 1866916418141814784 |
|---|---|
| author | Onn, Shmuel |
| author_facet | Onn, Shmuel |
| contents | We show that a circuit walk from a given feasible point of a given linear program to an optimal point can be computed in polynomial time using only linear algebra operations and the solution of the single given linear program.
We also show that a Graver walk from a given feasible point of a given integer program to an optimal point is polynomial time computable using an integer programming oracle, but without such an oracle, it is hard to compute such a walk even if an optimal solution to the given program is given as well.
Combining our oracle algorithm with recent results on sparse integer programming, we also show that Graver walks from any point are polynomial time computable over matrices of bounded tree-depth and subdeterminants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_00656 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Circuit and Graver Walks and Linear and Integer Programming Onn, Shmuel Optimization and Control Discrete Mathematics Data Structures and Algorithms Combinatorics 05A, 15A, 51M, 52A, 52B, 52C, 62H, 68Q, 68R, 68U, 68W, 90B, 90C We show that a circuit walk from a given feasible point of a given linear program to an optimal point can be computed in polynomial time using only linear algebra operations and the solution of the single given linear program. We also show that a Graver walk from a given feasible point of a given integer program to an optimal point is polynomial time computable using an integer programming oracle, but without such an oracle, it is hard to compute such a walk even if an optimal solution to the given program is given as well. Combining our oracle algorithm with recent results on sparse integer programming, we also show that Graver walks from any point are polynomial time computable over matrices of bounded tree-depth and subdeterminants. |
| title | Circuit and Graver Walks and Linear and Integer Programming |
| topic | Optimization and Control Discrete Mathematics Data Structures and Algorithms Combinatorics 05A, 15A, 51M, 52A, 52B, 52C, 62H, 68Q, 68R, 68U, 68W, 90B, 90C |
| url | https://arxiv.org/abs/2410.00656 |