WorksComputer Science
Canonical Truncation for Mixed-Integer and Combinatorial n-Fold Optimization
Abstract
We consider a special block-structured integer program with blocks. Every block has a prescribed number of vectors that need to be selected while minimizing the objective , where is a rational cost vector, is an integral matrix with rows, and is an arbitrary function. We access via an oracle that minimizes when all but variables are fixed. Our algorithm runs in time where is the largest absolute value of an entry in , is the necessary time to evaluate the oracle for and is the size of the input. This model is a variation of the model studied by Dadush et al.~[IPCO 23]. Their model has only a single block but individual upper and lower bounds on the variables instead of prescribed block sums. For their model they present an algorithm with running time where is the number of variables. We use our algorithm to solve mixed-integer linear programs with no upper bounds on the variables, a linear objective, and arbitrarily many constraints involving only fractional variables in time , where is the number of constraints involving integral variables and is the largest absolute value of coefficients of integral variables. This improves the dependence on in the exponent to asymptotically match the dependency in the integer setting. Further, we use our algorithm to generalize the parameterized algorithm for scheduling on uniformly related machines by Rohwedder~[ICALP 25] to obtain an algorithm for multiple knapsack with running time where is the maximum weight of an item and the number of different weights.
Funding. Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project number 528381760.
Introduction
We study the following block-structured integer program. Let be integers. For each block , let and be positive integers, and set . For , let denote its block of consecutive coordinates, starting at . Let , , and . Set where is the largest absolute value of an entry in . We consider
We optimize for the combination of and applied to the linking image while every prescribed block sum, i.e., , is satisfied. We are given via an oracle with the following low-dimensional optimization assumption. Given a partition K\mathbin{\mathaccent\cdot\cup}J of , the coordinates with indices in are fixed and determined by the vector . Further, we have . The oracle solves
where and are the restrictions to the columns given by and respectively. and contain the coordinates of and , respectively, belonging to the original block . The oracle reports infeasibility in case no feasible integer point exists due to the supplied and . If the optimum is , it is returned symbolically. Let be the necessary time to evaluate the oracle (2), return the optimal value, and a corresponding solution.
Theorem 1.1. Under the oracle assumption in (2), the problem (1) can be solved in time.
An evaluation oracle for an arbitrary does not suffice for the claimed bound. When , , , and , the problem is , which requires evaluation oracle calls for arbitrary functions.
Our oracle model is an adaptation of the one by Dadush et al. [7]. They optimize with lower and upper bounds for , where has entries bounded by , assuming that optimization is possible when all but variables are fixed. Their algorithm has running time , where again is the cost of the oracle. The factor can be absorbed into the parameter dependence in several special cases. Hunkenschröder et al. [11] considered the 0/1 variant with the restriction of to special convex functions. Their assumed oracle provides the function value and the gradient at the queried point. They obtain an algorithm even when is unknown under certain conditions.
Applications
Mixed-Integer Linear Programming
Let , , , , and , where . Let be an explicitly given rational polyhedron, and set . We consider the following mixed-integer linear program
To solve (3), we apply Theorem 1.1 for a single block together with a calculated block sum while encoding the fractional part of (3) in (as done in [7]). We solve the corresponding oracle using the algorithm of Lenstra with Kannan’s improvement [20, 16], which solve MILPs in time . This yields the following result.
Theorem 1.2. The MILP (3) can be solved in time.
Dadush et al. [7 Corollary 3] already consider a closely related mixed-integer model with upper bounds on the integer variables, arbitrary coefficients on the continuous variables, and additional constraints involving only those variables. Their bound is . Without integer-variable upper bounds or the linear objective, the factor can be omitted. The running time for the MILP (3) was also achieved in [Roh19]. Thus, our contribution is reducing the dependence on in the exponent, which asymptotically matches the best known dependence on in the exponent for pure non-negative integer linear programming [8, 15]. Brand et al. [1] give algorithms for separable convex mixed-integer optimization with few rows, with parameter dependence for the full constraint matrix , where is the number of rows in . Compared to (3), extra constraints for the fractional variables outside of are not permitted in their model.
Combinatorial -fold
Let , , and the positive block totals be as in (1), and let . Let be a separable discrete convex function, i.e., is non-decreasing in for every . We consider the combinatorial -fold problem
Knop et al. [18] introduced the combinatorial -fold model that specializes -fold IPs by restricting the block-local matrices to rows containing only ones. Our addition is the separable convex cost on the linking image .
Theorem 1.3. The combinatorial -fold (4) can be solved in time, assuming that can be evaluated exactly in time .
For linear objectives and a fixed linking right-hand side, Jansen et al. [14] already obtain parameter dependence with logarithmic dependence on the right-hand side. The same asymptotic dependency on , , and was also achieved by Rohwedder [23] and Gupta et al. [9] but both algorithms have a linear dependence on the total prescribed block sums. None of the just mentioned algorithms are able to handle non-linear objectives. Notable about this line of research is that the quadratic dependence on the number of linking constraints in the exponent of -fold algorithms (e.g. [CEH+21]) is replaced by introducing the number of blocks into the base of the parameter term.
Multiple Knapsack
An instance of Multiple Knapsack consists of item types with positive integer weights , nonnegative rational profits , and integer multiplicities , together with knapsacks of integer capacities . The task is to select and assign items to the knapsacks without exceeding their capacities or the available multiplicities, maximizing the total profit. All numbers, including the multiplicities, are encoded in binary. Let be the number of distinct item weights and let be the largest weight. A running time of already follows directly from a straightforward -fold IP formulation with classic convex costs and standard -fold algorithms [17]: the formulation has linking constraints for the weight classes, one local capacity constraint per knapsack, and an additional block recording rejected items and their profits.
We remove the quadratic dependence on in the exponent by combining our combinatorial -fold algorithm with a modular reduction for scheduling on uniformly related machines by Rohwedder [23].
Theorem 1.4. Multiple Knapsack can be solved in time .
Note that the dependence on cannot be removed: the reduction of Koutecký and Zink [19 Theorem 4.13] for scheduling on uniformly related machines implies that Multiple Knapsack is NP-hard already for and unit profits, and hence is not in XP parameterized only by unless P = NP. A lower bound follows under the Satisfiability Hypothesis (SH) of Stearns and Hunt [SH90]: for every fixed , there is no -time algorithm, even with identical capacities and unit profits. Indeed, the reduction of Chen, Jansen, and Zhang [4] maps a 3SAT instance of size to jobs with polynomially bounded processing times. Such an algorithm would therefore solve 3SAT in time , contradicting SH.
Other parameterizations and approximation algorithms have also been studied for the classical formulation with explicitly listed items (see e.g., [5, 10, 12, 13]).
Technical Overview
The core idea of our algorithm is the classic paradigm to focus on optimal solutions with special structure. Since the evaluation of only depends on the linking image, the concrete assignment of the variables only matters for the linear objective . For a fixed linking image, we choose a representative candidate from the set of optimal solutions according to . In particular, we choose the lexicographically (lexicographic order denoted by ) smallest solution. We call these solutions canonical. Considering the lexicographically smallest solution is a common approach, see for example [24]. Therefore, our contribution is applying this technique in our proposed setting and its application.
Canonical solutions have inherently small support: the number of non-zero coordinates in every block is bounded by a function in and . Further, the number of blocks with multiple big coordinates (coordinates exceeding a certain threshold) and the total number of big coordinates in these blocks is bounded by . The proofs for the structural properties rely on the fact that the variables have no individual upper bounds. These structural properties allow us to define truncated canonical solutions, which can be efficiently enumerated while retaining all the necessary information to invoke the oracle. This is in contrast to the approach used in [7], which builds on the proximity for ILPs in [8] and combines it with a guessing procedure to apply the oracle.
Properties of Canonical Solutions
We define
The function is well-defined, since is contained in the finite candidate set for . Call canonical if it is a fixpoint of , i.e., . Replacing an optimal solution by its canonical representative preserves all constraints and cannot increase its linear cost. Consequently a canonical optimum exists.
First, we show that being canonical is hereditary in the sense that all subvectors of a canonical vector are also canonical. is a subvector of if for all . We denote this by .
Lemma 2.1. Let be canonical. Then every with is also canonical.
Proof. Let such that . Towards a proof by contradiction, suppose . Set . Since and for all , we have and for all . If we have . Otherwise, if and we have and . Both cases contradict that is a fixpoint of , which implies .
A direct implication of this lemma is that all subvectors of a canonical solution have a different linking sum or block sum.
Corollary 2.2. Let be canonical. Then, for with , and for all implies .
Proof. Let with , and for all . Thus, the candidate set for and is the same and since and , we have .
This fact is important for the structural properties we show next since it enables counting arguments. We start by showing that a canonical solution inherently has small support in every block. The support of a vector is defined as .
Lemma 2.3. Let be canonical. Then
Proof. Towards a proof by contradiction, suppose that there is an such that . Set with . For every we have and . Hence, the number of possible images is bounded by . Since for every integer , we have
where the last inequality uses . Thus two different vectors in have the same linking image and all block sums, which contradicts Corollary 2.2.
We call the coordinate in a solution big if and small otherwise. The set of big coordinates for block is denoted by
If a block has only a single big coordinate its value is fully determined by the assignment of the small variables in the block and . Under the assumption that we know the values of all small coordinates, these can be determined in the algorithm without invoking the oracle. Thus, we are only interested in the total number of big coordinates in blocks with at least two big coordinates. This number is in as shown by the following lemma.
Lemma 2.4. Let be canonical. Then
Proof. Suppose there are disjoint pairs of big coordinates in , with each pair contained in a single block. We build different subvectors of . Given a vector set and for all . Set all other coordinates to zero and call this vector . All these vectors are subvectors of and hence canonical. Further, all constructed vectors share the same block sums and . Thus there are at most different linking images but which contradicts Corollary 2.2.
The maximum number of distinct disjoint pairs in block is . It follows that
Since for , we obtain the claimed bound.
Next, we truncate all big coordinates in canonical vectors such that we still retain the information which coordinates are big and are able to enumerate all truncated vectors efficiently.
Lemma 2.5. Let be canonical with for . Then there exists a truncation of such that
, hence, by heredity is canonical,
,
, and
for all .
Proof. We construct from . Start with where the entries are given by . Its sum in block is less than by Lemmas 2.1 and 2.3, and at most . Increase its coordinates integrally, never exceeding , until in every block. This is possible since . The resulting vector satisfies all claimed properties.
Algorithm
The algorithm works by first enumerating all truncated candidates as defined by Lemma 2.5. Then for every candidate we fix all fully determined variables and solve the remaining problem with the oracle given in (2).
We start by eliminating duplicate columns in every block. Within each block, merge variables whose columns in agree, retaining one of minimum linear cost. Since we only have prescribed block sums and no individual lower/upper bounds for variables, this transformation preserves all the necessary structure. After this step, the number of variables is bounded by . In the following we use the same notation for the reduced instance.
Define the set of truncated candidates with the bounds given in Lemma 2.5
This set can be enumerated efficiently using straightforward dynamic programming.
Lemma 3.1. can be enumerated in time.
Proof. We use a dynamic program processing blocks in order and inserting units into block , one at a time. At layer , for , let store the minimum-cost, lexicographically smallest vector with linking image , block sums for , sum in block , and zero in later blocks. Start with the zero vector at image zero. The initial layer of each block is the preceding block’s final layer, and for the recurrence is
where is the th column of in block and is the unit vector corresponding to the th variable in block . Removing a positive coordinate from any candidate gives a predecessor. Replacing this predecessor by the stored minimum-cost, lexicographically smallest representative cannot worsen the resulting vector. Induction therefore proves the recurrence.
The preprocessing can be done in time . For all states , we have since . Every state has at most potential predecessors and thus a state can be calculated in . Since is the last layer of the dynamic program, it can be enumerated in time
Proof. If , then , and every column of belongs to . Retain a minimum-cost variable for each column value and fix all other variables to zero. This preserves an optimum and leaves at most free variables, so a single oracle call solves the problem in time. Henceforth assume .
The remaining part of the algorithm is to apply the oracle. For each truncated candidate , we define a set and vector to supply to the oracle. is the set of all indices corresponding to small coordinates in , i.e., , and all indices of big coordinates that are the only big coordinate in their block. For all indices corresponding to small coordinates, we set . Let be the index of the single big coordinate in block . We set . Finally set . We have by Lemma 2.4. We call the oracle (2) with and . Discard the result if the oracle reports infeasibility. Return the best solution over all candidates, which may be when all feasible oracle calls return this value.
Let be an optimal canonical solution. By Lemma 2.5 and the definition of the truncated version of will be considered by the algorithm. Let and be the set and vector constructed in the iteration of . We have for all by property 4 of Lemma 2.5 and the fact that the value for a unique big coordinate in a block is fully determined by the values of the small variables. Thus, the oracle in this iteration finds a solution at least as good as .
The preprocessing and enumerating the set takes time by Lemma 3.1. The number of oracle calls is bounded by . Since when , we obtain the claimed running time.
Applications
MILP
Theorem 1.2. The MILP (3) can be solved in time.
Proof. We start by solving the LP relaxation of (3). If the LP relaxation is infeasible, then so is the MILP, and we are done. Since all data are rational, if the LP relaxation has an optimal solution, the MILP is either infeasible or has an optimal solution; if the LP relaxation is unbounded below, the MILP is either infeasible or also unbounded below [21].
Suppose first that the LP relaxation has an optimal solution. For fixed , the constraints on depend on only through . To express the MILP in the form required by Theorem 1.1, define, for ,
All nonempty LPs defining have the same recession directions, namely those of that lie in . An improving direction would also make the original LP relaxation unbounded below, so every nonempty LP defining has a finite, attained rational minimum. The MILP therefore reduces to minimizing over , where excludes choices of that admit no feasible .
To apply Theorem 1.1 with one block and , we also need a prescribed sum of the integer coordinates. We will obtain this by bounding and adding a slack variable. The bound must preserve an optimal solution whenever one exists and have polynomial binary encoding length. Let be the optimal LP solution computed above, chosen with polynomial encoding length. Let be the integer constraint matrix obtained by writing the full constraint system as inequalities and clearing denominators row by row, and set and . Its square subdeterminants have absolute value at most . Thus, by the mixed-integer proximity bound in [3 Remark 1], converting from the infinity norm to the 1-norm, whenever the MILP is feasible it has an optimal solution with .
The positive integer is computable in polynomial time and has polynomial encoding length. Set . Then has polynomial encoding length and . Denominator clearing is used only to derive this bound; the reduction retains the original linking matrix .
Introduce with zero cost and a zero linking column, so that . Write , , and . We obtain
This has one block, linking rows, and coefficient bound . It has a finite optimum exactly when the MILP (3) is feasible, and then preserves its optimal value.
It remains to implement the oracle in (2) for this choice of . For a given partition with and , first check whether the block-sum constraint admits a nonnegative integer completion, reporting infeasibility otherwise. Substituting the definition of then gives the MILP
If this MILP is infeasible, the oracle returns together with any nonnegative integer completion of the block sum. Otherwise, it returns an optimal integer vector and the corresponding objective value. In all calls generated by the algorithm, the fixed coordinates are at most , so the oracle inputs have polynomial encoding length. Since this MILP has only integer variables, it can be solved in time [20, 16]; the continuous dimension affects only the polynomial factor. Applying Theorem 1.1 now gives
If the returned optimum is , the original MILP is infeasible. Otherwise, discard the slack coordinate and solve the LP defining for the returned to recover an optimal continuous vector .
Finally, if the original LP relaxation is unbounded below, apply the preceding procedure with both objective vectors set to , starting with an LP solution for this zero objective. This decides mixed-integer feasibility within the same running time: if no feasible point exists, report infeasibility; otherwise, the original MILP is unbounded below. □
Combinatorial n-fold
The block-sum constraints restrict the possible solutions, which implies where for all that adheres to the prescribed block sums.
Theorem 1.3. The combinatorial n-fold (4) can be solved in time, assuming that can be evaluated exactly in time .
Proof. To express the combinatorial n-fold (4) in the form required by Theorem 1.1, define, for ,
Then Equation (4) is precisely Equation (1) with this choice of . The block totals are already prescribed, so it remains to implement the oracle in Equation (2).
For a given partition with and , first check whether the block-sum constraints admit a nonnegative integer completion, reporting infeasibility otherwise. If they do, retain one such completion. The finite-valued part of the oracle is
Introducing integer variables for the linking image gives the equivalent separable convex integer program
We solve (6) using Theorem 7.1.2 in [6]. Put . The block sums imply for every free variable in block , and for every . These coordinate bounds have polynomial encoding length in .
Let be the sum of the linear interpolations of the on ; it is convex and agrees with at integer points. For , let be the real relaxation of (6), with the coordinate bounds above and . To strongly separate a query , first check the explicit linear constraints and return any violated constraint, orienting equalities appropriately. Otherwise, set
for , where is the -th unit vector. Separability and discrete convexity imply throughout the box, with equality at . If , report membership in . Otherwise, return the valid separating inequality
which is strictly violated at the query point; a zero normal certifies . This oracle uses evaluations of at integer points in and polynomial-time rational arithmetic, with separating inequalities of polynomial encoding length in and the encoding length of . Also, lies in the Euclidean ball of radius centered at the origin.
Dadush’s deterministic integer-feasibility algorithm [6 Theorem 7.1.2] therefore solves each objective-threshold query in time. Since exact polynomial-time evaluation implies polynomial encoding length for all feasible integer objective values, binary search requires only polynomially many such queries to obtain an exact minimizer. Thus (6) can be solved deterministically in
If this program is infeasible, the oracle returns together with the retained block-sum completion; otherwise, it returns an optimal and its objective value. The returned vector and any finite objective value have polynomial encoding length. Applying Theorem 1.1 now gives
If the returned optimum is , the original problem is infeasible. Otherwise, the algorithm returns an optimal .
Multiple Knapsack
Theorem 1.4. Multiple Knapsack can be solved in time .
Proof sketch. Adding zero-profit items of weight one allows every knapsack to be filled exactly and introduces at most one additional weight class. Since the total available profit is fixed, we minimize rejection cost. For each weight class , let be the cost of rejecting its cheapest items. Its marginal costs are nondecreasing, so is discrete convex.
We apply Rohwedder’s modular construction [23]. Knapsacks of capacity at least are big; the others are small. We guess a pivot class and reserve pivot items in total, where is the set of big knapsacks. Small knapsacks are represented by full configurations. For big knapsacks, removing pivot items and bundles of equal-weight nonpivot items leaves bounded residual configurations preserving the load modulo . A suitable pivot exists by the pigeonhole principle, and its reserve guarantees that the bundles can be distributed before inserting the pivot items.
Grouping small knapsacks by capacity and big knapsacks by residue modulo gives a combinatorial -fold structure with configuration blocks and one bundle block. Applying Theorem 1.3 to each pivot gives a running time of . Appendix § 6 gives the full formulation, correctness proof, and reconstruction.
Generative AI Disclosure
ChatGPT Astra suggested algorithms for MILPs and the presented combinatorial -fold extension using the lexicographical minimal solutions. The authors combined them to the model presented in this paper. ChatGPT Astra was also used to polish the text in the paper. The authors take full responsibility for the content of the document.
Full Proof for Multiple Knapsack
Since the total profit of all available items is fixed, maximizing the profit of selected items is equivalent to minimizing the total profit of the items not selected. We regard the profit of an unselected item as its rejection cost. Items of the same weight can then be grouped: if a prescribed number of them is to be rejected, it is optimal to reject the cheapest ones. This gives a separable convex rejection cost. We combine this observation with the modular pivot construction of Rohwedder [23] and Theorem 1.3.
Put . We assume , since otherwise selecting the most profitable items is optimal. Add dummy items of weight one and profit zero. Every packing can now be filled to capacity without changing its profit, and discarding dummy items recovers a packing of the original instance. Group the augmented items by weight, merging the dummies with any real items of weight one. Adding the dummies introduces at most one new weight class, which is absorbed in the running-time bound. Thus, without loss of generality, we continue to write for the number of weight classes after augmentation. Index these classes by their distinct weights , with multiplicities . In particular, . For and , let be the total rejection cost of the cheapest items of weight . The differences are nondecreasing, so is discrete convex. Sorting the profit classes within each weight class gives a piecewise-linear interpolation with one segment per distinct profit. Its breakpoints are prefix sums of binary multiplicities. Thus the functions have polynomial encoding length and can be evaluated exactly in polynomial time. Extend them beyond their domains using their first and last segment slopes; these extensions remain convex.
To formulate the packing constraints, use Rohwedder’s modular construction [23] and set
Call the knapsacks in big and all others small. For each candidate pivot class satisfying , solve the formulation below. We take the best solution over all candidates. The formulation will reserve items of this class for the big knapsacks. If , then .
For a fixed pivot , group small knapsacks by their exact capacity and big knapsacks by their capacity modulo . Let be the set of nonempty classes and the number of knapsacks in class . There are at most classes. A small class of capacity has configurations
For a big class of residue , use the residual configurations
A bundle of a nonpivot class contains items, whereas a pivot bundle contains one item. Write for and .
Let count knapsacks using configuration , and let count bundles of class , excluding the reserved pivot items. The selected count outside the reserve is
Consequently, the number of rejected items for a given class is
We obtain the minimization problem
The last equality creates one additional block containing the bundle variables and a slack variable . It does not restrict the other variables: every bundle has weight at least one, so the total-weight inequality already implies . The reserve is accounted for both in the selected weight and in the rejection costs.
The correctness of this formulation follows essentially the same argument as Rohwedder [23 Sections 2 and 4].
Lemma A.1. For every , the following are equivalent:
The original instance admits a packing with rejection cost at most .
For some pivot class satisfying , Equation (7) admits a feasible solution with objective value at most .
Moreover, any feasible solution of Equation (7) can be converted into a packing with the same rejection cost in time polynomial in its encoding length and .
Proof. Take an optimal packing and fill its unused capacity with dummy items. Every big knapsack contains at least items, so by the pigeonhole principle, some weight class contributes at least items to the big knapsacks. Choose this class as the pivot; if there are no big knapsacks, choose any class. Keep the full configurations of the small knapsacks. From every big knapsack remove all pivot items and groups of nonpivot items of the same weight until fewer than of each nonpivot class remain. These removals preserve the load modulo . Reserve of the removed pivot items and record all other removed items as bundles. This gives a feasible solution of Equation (7). Within each weight class, the rejected items may be chosen to be the cheapest ones without changing feasibility. Hence the objective equals the rejection cost of an optimal packing.
Conversely, assign the configurations of a feasible solution to knapsacks of their classes. Small knapsacks are full. Every big residual configuration fits, since . Keep the pivot items aside and insert the nonpivot bundles first. At every stage, the total free space in the big knapsacks is at least the weight of all selected but unplaced items. In particular, it is at least . If , some big knapsack therefore has free space at least . Every nonpivot bundle has weight and can therefore be placed. Afterwards, all remaining free spaces are multiples of and their sum is at least . Thus all pivot items can also be placed. If , the small configurations already have total weight , so the weight inequality forces all bundle variables to zero.
Choose the rejected items in each class to be its cheapest items, assign the remaining copies to the constructed positions of that weight, and discard dummy items. This produces a packing with rejection cost exactly the objective of Equation (7). Taking the minimum over pivot choices therefore yields an optimal solution of the original instance. Bundle placement and the assignment of original profit classes can both be performed in batches, so reconstruction is polynomial in the input and output encoding lengths.
of Theorem 1.4. By Lemma A.1, it remains to solve Equation (7), which we do by applying Theorem 1.3. Use the inequalities involving as linking rows, and define
Each is discrete convex. The polynomial-time exact evaluation assumption of Theorem 1.3 holds by the piecewise-linear descriptions above. The formulation has linking rows and at most blocks, with coefficient bound . There are at most configurations. Their encoding, together with the rejection-cost functions, has length ; the number of profit classes affects only the polynomial factor.
Since and , there are at most linking rows and blocks. Applying Theorem 1.3 to each of the pivot choices therefore takes
time, including configuration enumeration and reconstruction.
References
- [1]C. Brand, M. Koutecký, A. Lassota, and S. Ordyniak. “Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds”. In: 32nd Annual European Symposium on Algorithms (ESA 2024). Vol. 308. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, 32:1–32:18. DOI: 10.4230/LIPIcs.ESA.2024.32.DOI
- [3]W. J. Cook, A. M. H. Gerards, A. Schrijver, and É. Tardos. “Sensitivity theorems in integer linear programming”. In: Math. Program. 34.3 (1986), pp. 251–264. DOI: 10.1007/BF01582230.DOI
- [4]L. Chen, K. Jansen, and G. Zhang. “On the Optimality of Approximation Schemes for the Classical Scheduling Problem”. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014). SIAM, 2014, pp. 657–668. DOI: 10.1137/1.9781611973402.50.DOI
- [5]C. Chekuri and S. Khanna. “A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem”. In: SIAM Journal on Computing 35.3 (2005), pp. 713–728. DOI: 10.1137/S0097539700382820.DOI
- [6]D. N. Dadush. “Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation”. PhD thesis. Georgia Institute of Technology, 2012. URL: http://hdl.handle.net/1853/44807.
- [7]D. Dadush, A. Léonard, L. Rohwedder, and J. Verschae. “Optimizing Low Dimensional Functions over the Integers”. In: Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Madison, WI, USA, June 21-23, 2023, Proceedings. Vol. 13904. Lecture Notes in Computer Science. Springer, 2023, pp. 115–126. DOI: 10.1007/978-3-031-32726-1_9.DOI
- [8]F. Eisenbrand and R. Weismantel. “Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma”. In: ACM Transactions on Algorithms 16.1 (2020), 5:1–5:14. DOI: 10.1145/3340322.
- [9]S. Gupta, P. Jain, S. Seetharaman, and M. Zehavi. “A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma”. In: 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Vol. 358. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, 14:1–14:17. DOI: 10.4230/LIPIcs.IPEC.2025.14.DOI
- [10]F. Gurski, C. Rehs, and J. Rethmann. “Knapsack Problems: A Parameterized Point of View”. In: Theoretical Computer Science 775 (2019), pp. 93–108. DOI: 10.1016/j.tcs.2018.12.019.DOI
- [11]C. Hunkenschröder, S. Pokutta, and R. Weismantel. “Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube”. In: SIAM J. Optim. 33.2 (2023), pp. 538–552. DOI: 10.1137/22M1489988.DOI
- [12]K. Jansen. “Parameterized Approximation Scheme for the Multiple Knapsack Problem”. In: SIAM Journal on Computing 39.4 (2009), pp. 1392–1412. DOI: 10.1137/080731207.DOI
- [13]K. Jansen. “A Fast Approximation Scheme for the Multiple Knapsack Problem”. In: SOFSEM 2012: Theory and Practice of Computer Science. Vol. 7147. Lecture Notes in Computer Science. Springer, 2012, pp. 313–324. DOI: 10.1007/978-3-642-27660-6_26.DOI
- [14]K. Jansen, K. Kahler, L. Pirotton, and M. Tutas. “New Algorithm for Combinatorial n-Folds and Applications”. In: 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Vol. 358. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, 15:1–15:15. DOI: 10.4230/LIPIcs.IPEC.2025.15.DOI
- [15]K. Jansen and L. Rohwedder. “On Integer Programming, Discrepancy, and Convolution”. In: Mathematics of Operations Research 48.3 (2023), pp. 1481–1495. DOI: 10.1287/moor.2022.1308.DOI
- [16]R. Kannan. “Minkowski’s Convex Body Theorem and Integer Programming”. In: Math. Oper. Res. 12.3 (1987), pp. 415–440. DOI: 10.1287/moor.12.3.415.DOI
- [17]D. Knop, M. Koutecký, A. Levin, M. Mnich, and S. Onn. “High-multiplicity N-fold IP via configuration LP”. In: Math. Program. 200.1 (2023), pp. 199–227. DOI: 10.1007/S10107-022-01882-9.DOI
- [18]D. Knop, M. Koutecký, and M. Mnich. “Combinatorial n-fold Integer Programming and Applications”. In: Mathematical Programming 184.1–2 (2020), pp. 1–34. DOI: 10.1007/s10107-019-01402-2.DOI
- [19]M. Koutecký and J. Zink. “Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines”. In: Journal of Scheduling 28.1 (2025), pp. 139–156. DOI: 10.1007/s10951-024-00827-8.
- [20]H. W. Lenstra Jr. “Integer Programming with a Fixed Number of Variables”. In: Math. Oper. Res. 8.4 (1983), pp. 538–548. DOI: 10.1287/moor.8.4.538.DOI
- [21]R. R. Meyer. “On the existence of optimal solutions to integer and mixed-integer programming problems”. In: Math. Program. 7.1 (1974), pp. 223–235. DOI: 10.1007/BF01585518.
- [23]L. Rohwedder. “ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines”. In: 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Vol. 334. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, 126:1–126:13. DOI: 10.4230/LIPIcs.ICALP.2025.126.
- [24]L. Rohwedder and K. Węgrzycki. “Space-Efficient Algorithm for Integer Programming with Few Constraints”. In: Integer Programming and Combinatorial Optimization - 26th International Conference, IPCO 2025, Baltimore, MD, USA, June 11–13, 2025, Proceedings. Vol. 15620. Lecture Notes in Computer Science. Springer, 2025, pp. 442–451. DOI: 10.1007/978-3-031-93112-3_32.