Integer programs with bounded subdeterminants and two nonzeros per row
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912209509023744 |
|---|---|
| author | Fiorini, Samuel Joret, Gwenaël Weltge, Stefan Yuditsky, Yelena |
| author_facet | Fiorini, Samuel Joret, Gwenaël Weltge, Stefan Yuditsky, Yelena |
| contents | We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than $k$ vertex-disjoint odd cycles, where $k$ is any constant. Previously, polynomial-time algorithms were only known for $k=0$ (bipartite graphs) and for $k=1$.
We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to $b$-matching. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2106_05947 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Integer programs with bounded subdeterminants and two nonzeros per row Fiorini, Samuel Joret, Gwenaël Weltge, Stefan Yuditsky, Yelena Combinatorics Discrete Mathematics Data Structures and Algorithms Optimization and Control We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than $k$ vertex-disjoint odd cycles, where $k$ is any constant. Previously, polynomial-time algorithms were only known for $k=0$ (bipartite graphs) and for $k=1$. We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to $b$-matching. |
| title | Integer programs with bounded subdeterminants and two nonzeros per row |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2106.05947 |