A simple algorithm for Combinatorial n-fold ILPs using the Steinitz Lemma
Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, Meirav Zehavi · 2025
Read A simple algorithm for Combinatorial n-fold ILPs using the Steinitz Lemma by Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, Meirav Zehavi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-03766.txt.
Introduction
Sushmita Gupta and co-authors give a simple algorithm for a class of integer programs in a 2025 paper. N-fold programs repeat one small block many times in a structured way. Combinatorial versions of these programs capture hard problems from many different domains.
Older methods augment a starting solution step by step toward the optimum. Others relax the program or use proximity arguments to bound the search. Their method applies a classic Steinitz lemma directly to the problem structure. Variables are unbounded but must stay non-negative throughout. Input structure decides the final run time behavior of the method. Readers in algorithm design get a cleaner route through a heavily studied problem family.
Catalog record
| CREATOR | Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, Meirav Zehavi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-03766
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A simple algorithm for Combinatorial n-fold ILPs using the Steinitz Lemma Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, Meirav Zehavi Abstract We present an algorithm for a class of n n -fold ILPs: whose existing algorithms in literature typically (1) are based on the 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 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 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. The Institute of Mathematical Sciences, HBNI, Chennai, [email protected] IIT Jodhpur, Jodhpur, [email protected] The Institute of Mathematical Sciences, HBNI, Chennai, [email protected] Ben-Gurion University of the Negev, Beer-Sheva, [email protected] \Crefname claim-inside-theoremClaimClaims \Crefname lemma-inside-theoremLemmaLemmas \Crefname claim-inside-lemmaClaimClaims ccs Theory of computation Integer programming keywords n -fold integer linear program, parameterized algorithms † † runningauthor: S. Gupta, P. Jain, S. Seetharaman, and M. Zehavi † † copyright: Jane Open Access and Joan R. Public † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The power of the linear algebra method has a long and storied history in the design and analysis of algorithms, [ 3 , 31 ] . The question of reordering vectors so that all partial sums are bounded was posed by mathematicians Paul Lévy and George Riemann in the early 20th century. The question was first affirmatively answered by Ernst Steinitz [ 32 , 15 ] showing that such a reordering of vectors, that sum to zero and are all in a unit ball with respect to any arbitrary norm, is indeed possible where all the partial sums can be bounded by a constant that depends only on d , the dimension of the vectors. This result, now eponymously known as the Steinitz Lemma, stated in \Cref thm:steinitz-lemma, has become a cornerstone in our understanding of the geometry of numbers and has led to numerous algorithmic applications centered around problems that have an integer linear program (ILP) formulation. In this paper, we study a simple Steinitz Lemma based non-augmenting algorithm for a class of combinatorial n -fold ILPs. The usefulness of Steinitz Lemma in modern algorithmic research is perhaps best underscored by its applicability to analyze integer linear programs (ILP), as exhibited by Eisenbrand et al. [ 12 ] who improved upon the longstanding best bound of Papadimitriou [ 28 ] . Papadimitriou’s seminal work gave a simpler proof of ILPs being in NP and the first pseudo-polynomial algorithm when the number of constraints is constant. This can be viewed as a pseudo-parameterized algorithm with respect to the number of constraints. Subsequently, Jansen et al. [ 19 ] further improved the running time by applying the Steinitz Lemma in an alternative way. Due to the versatility of the LP framework, this connection has unlocked a promising direction of research fueled by a geometric perspective and is likely to pay rich dividends for years to come. In this paper, we are continuing this line of investigation by employing Steinitz Lemma on a special class of ILPs for the purpose of obtaining better bounds. Notwithstanding these exciting possibilities, the bottom line is that solving an ILP is known to be NP - complete and that poses a computational challenge when we desire integral solutions only. While we know of certain classes of ILPs, such as totally unimodular , bimodular [ 2 ] , binet [ 1 ] that can be solved in polynomial time, the task of mapping the ILP landscape into families that are tractable under modest restrictions is ongoing. In particular, in recent times researchers are motivated to design parameterized algorithms because they behave like polynomial-time algorithms when the parameter is constant-valued. An algorithm is said to be fixed-parameter tractable ( FPT ) with respect to parameters k_{1},\dots,k_{\ell} , if its running time is of the form f(k_{1},\dots,k_{\ell})\cdot|\text{input}|^{\mathcal{O}(1)} for some computable function f . Steinitz Lemma has proven to be useful even in this direction of research, as exhibited in its usefulness in the study of block-structured ILPs. Block-structured ILP In recent years, a class of block structured programs called the n - fold ILP has come to sharp focus due to their relevance to efficiently solving problems in scheduling [ 22 ] , fair division [ 27 ] , and social choice [ 25 ] to name a few. For example, in the high-multiplicity scheduling setting, the input is succinctly encoded by partitioning the jobs (machines) into types such that all jobs (machines) within a type are identical. Note that the number of job (machine) types can be much smaller than the number of jobs (machines). Using n -fold ILP, Knop et al. [ 22 ] obtain algorithms for some scheduling problems that are FPT with respect to the number of job (machine) types. More broadly, the n -fold setting has unlocked the door towards parameterized and approximation algorithms and their rich tool-kit. Formally, we define n -fold ILP as the following \min\left\{c^{\intercal}x\,\mid\mathscr{A}x=b\,,\ell\leq x\leq u\,,x\in\mathbb{Z}^{nt}\right\}, where vectors c,\ell,u\in\mathbb{Z}^{nt},b\in\mathbb{Z}^{r+ns} and the constraint matrix \displaystyle\mathscr{A}:=\left(\begin{array}[]{cccc}T&T&\cdots&T\\ D&0&\cdots&0\\ 0&D&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&D\\ \end{array}\right),\text{such that} the top block T\in\mathbb{Z}^{r\times t} and the diagonal block D\in\mathbb{Z}^{s\times t} . Let \Delta_{X} denote an upperbound on the absolute value of an entry in a matrix X , and let \Delta_{I} denote the same for the numbers in the input. Hemmecke et al. [ 16 ] were the first to give an FPT algorithm for ( 1 ) with respect to the parameters \Delta_{\mathscr{A}},r,s,t . This algorithm runs in time \mathcal{O}(n^{3}t^{3}\cdot\Delta_{\mathscr{A}}^{\mathcal{O}(t(rs+st))}\log(\Delta_{c})) . Hence, this has better performance than [ 28 ] and [ 12 ] that work for general ILPs. Subsequently, Eisenbrand et al. [ 9 ] , using the Steinitz Lemma in a manner similar to [ 12 ] , improved the result of [ 16 ] , in terms of the dependence on t given that t\geq r,s . Their algorithm has running time n^{2}t^{2}\log\Delta_{I}\log^{2}{nt}\cdot(rs\Delta_{\mathscr{A}})^{\mathcal{O}(r^{2}s+rs^{2})}+\mathbf{LP} , where \mathbf{LP} denotes the time needed to solve the LP relaxation of ( 1 ). This is an FPT algorithm with respect to the parameters r,s,\Delta_{\mathscr{A}} . We are naturally interested in algorithms with smaller dependence on t , the number of columns, because t can be as large as \Delta_{\mathscr{A}}^{r+s} , a common occurrence in applications involving configuration IPs, as noted in [ 9 ] . Koutecky et al. [ 26 ] showed an algorithm that runs in time (nt)^{6}\log(nt)\cdot(rs\Delta_{\mathscr{A}})^{\mathcal{O}(r^{2}s+rs^{2})}+\mathbf{LP} . This is the first strongly polynomial time algorithm for fixed values of r,s,\Delta_{\mathscr{A}} .