A simple algorithm for Combinatorial n-fold ILPs using the Steinitz Lemma
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915372213469184 |
|---|---|
| author | Gupta, Sushmita Jain, Pallavi Seetharaman, Sanjay Zehavi, Meirav |
| author_facet | Gupta, Sushmita Jain, Pallavi Seetharaman, Sanjay Zehavi, Meirav |
| contents | We present an algorithm for a class of $n$-fold ILPs: whose existing algorithms in literature typically (1) are based on the \textit{augmentation framework} where one starts with an arbitrary solution and then iteratively moves towards an optimal solution by solving appropriate programs; and (2) require solving a linear relaxation of the program. Combinatorial $n$-fold ILPs is a class introduced and studied by Knop et al. [MP2020] that captures several other problems in a variety of domains. We present a simple and direct algorithm that solves Combinatorial $n$-fold ILPs with unbounded non-negative variables via an application of the Steinitz lemma, a classic result regarding reordering of vectors. Depending on the structure of the input, we also improve upon the existing algorithms in literature in terms of the running time, thereby showing an improvement that mirrors the one shown by Rohwedder [ICALP2025] contemporaneously and independently. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_03766 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A simple algorithm for Combinatorial n-fold ILPs using the Steinitz Lemma Gupta, Sushmita Jain, Pallavi Seetharaman, Sanjay Zehavi, Meirav Data Structures and Algorithms We present an algorithm for a class of $n$-fold ILPs: whose existing algorithms in literature typically (1) are based on the \textit{augmentation framework} where one starts with an arbitrary solution and then iteratively moves towards an optimal solution by solving appropriate programs; and (2) require solving a linear relaxation of the program. Combinatorial $n$-fold ILPs is a class introduced and studied by Knop et al. [MP2020] that captures several other problems in a variety of domains. We present a simple and direct algorithm that solves Combinatorial $n$-fold ILPs with unbounded non-negative variables via an application of the Steinitz lemma, a classic result regarding reordering of vectors. Depending on the structure of the input, we also improve upon the existing algorithms in literature in terms of the running time, thereby showing an improvement that mirrors the one shown by Rohwedder [ICALP2025] contemporaneously and independently. |
| title | A simple algorithm for Combinatorial n-fold ILPs using the Steinitz Lemma |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.03766 |