تقرير
Integer programs with bounded subdeterminants and two nonzeros per row
| العنوان: | Integer programs with bounded subdeterminants and two nonzeros per row |
|---|---|
| المؤلفون: | Fiorini, Samuel, Joret, Gwenaël, Weltge, Stefan, Yuditsky, Yelena |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, Mathematics - 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. Comment: v3: minor changes. v2: minor changes, accepted at FOCS 2021 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2106.05947 |
| رقم الأكسشن: | edsarx.2106.05947 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |