In this article, we study the computational complexity of solving a class of block structured integer programs (IPs), the so-called multistage stochastic IPs. A multistage stochastic IP is an IP of the form min { c T x | Ax = b , x ≥ 0, x integral} where the constraint matrix \({A}\) consists of small block matrices ordered on the diagonal line, and for each stage there are larger blocks with few columns connecting the blocks in a treelike fashion. Over the past few years there was enormous progress in the area of block structured IPs. For many of the known block IP classes, such as n -fold, tree-fold, and two-stage stochastic IPs, nearly matching upper and lower bounds are known concerning their computational complexity. One of the major gaps that remained, however, was the parameter dependency in the running time for an algorithm solving multistage stochastic IPs. Previous algorithms require a tower of t exponentials, where t is the number of stages. In contrast, only a double exponential lower bound was known based on the exponential time hypothesis. In this article, we show that the tower of t exponentials is actually not necessary. We show an improved running time of \(2^{(d\Vert A \Vert _\infty)^{\mathcal {O}(d^{3t+1})}} \cdot rn\log ^{\mathcal {O}(2^d)}(rn)\) for the algorithm solving multistage stochastic IPs, where d is the sum of columns in the connecting blocks and rn is the number of rows. Hence, we obtain the first bound by an elementary function for the running time of an algorithm solving multistage stochastic IPs. In contrast to previous works, our algorithm has only a triple exponential dependency on the parameters and only doubly exponential for every constant t . By this, we come very close to the known double exponential bound that holds already for two-stage stochastic IPs, i.e., multistage stochastic IPs with two stages. The improved running time of the algorithm is based on new bounds for the proximity of multistage stochastic IPs. The idea behind the bound is based on generalization of a structural lemma originally used for two-stage stochastic IPs. While the structural lemma requires iteration to be applied to multistage stochastic IPs, our generalization directly applies to inherent combinatorial properties of multiple stages. Already a special case of our lemma yields an improved bound for the Graver complexity of multistage stochastic IPs.

The starting point of this paper is the problem of scheduling n jobs with processing times and due dates on a single machine so as to minimize the total processing time of tardy jobs, i.e., 1 || ΣpjUj. This problem was identified by Bringmann et al. (Algorithmica 2022) as a natural subquadratic-time special case of the classic 1 || Σ wjUj problem, which likely requires time quadratic in the total processing time P, because of a fine-grained lower bound. Bringmann et al. obtain their Õ(P7/4) time scheduling algorithm through a new variant of convolution, dubbed Max-Min Skewed Convolution, which they solve in Õ(n7/4) time. Our main technical contribution is a faster and simpler convolution algorithm running in Õ(n5/3) time. It implies an Õ(P5/3) time algorithm for 11 | ΣpjUj, but may also be of independent interest.

Consider positive integral solutions to the equation a0x0 + … + anxn = t. In the so called unbounded subset sum problem, the objective is to decide whether such a solution exists, whereas in the Frobenius problem, the objective is to compute the largest t such that there is no such solution. In this paper we study the algorithmic complexity of the unbounded subset sum, the Frobenius problem and a generalization of both problems. More precisely, we study pseudo-polynomial time algorithms with a running time that depends on the smallest number a0 or respectively the largest number an. For the parameter a0, we show that all considered problems are subquadratically equivalent to (min, +)-convolution, a fundamental algorithmic problem from the area of fine-grained complexity. By this equivalence, we obtain hardness results for the considered problems (based on the assumption that an algorithm with a subquadratic running time for (min, +)-convolution does not exist) as well as algorithms with improved running time. The proof for the equivalence makes use of structural properties of solutions, a technique that was developed in the area of integer programming. In case of the complexity of the problems parameterized by an, we present improved algorithms. For example we give a quasi linear time algorithm for the Frobenius problem as well as a hardness result based on the strong exponential time hypothesis.

In this paper we study the computational complexity of solving a class of block structured integer programs (IPs) - so called multistage stochastic IPs. A multistage stochastic IP is an IP of the form where the constraint matrix consists of small block matrices ordered on the diagonal line and for each stage there are larger blocks with few columns connecting the blocks in a tree like fashion. Over the last years there was enormous progress in the area of block structured IPs. For many of the known block IP classes - such as n-fold, tree-fold, and two-stage stochastic IPs, nearly matching upper and lower bounds are known concerning their computational complexity. One of the major gaps that remained however was the parameter dependency in the running time for an algorithm solving multistage stochastic IPs. Previous algorithms require a tower of t exponentials, where t is the number of stages, while only a double exponential lower bound was known. In this paper we show that the tower of t exponentials is actually not necessary. We can show an improved running time for the algorithm solving multistage stochastic IPs with a running time of , where d is the sum of columns in the connecting blocks and n is the number of blocks on the lowest stage. Hence, we obtain the first bound by an elementary function for the running time of an algorithm solving multistage stochastic IPs. In contrast to previous works, our algorithm has only a triple exponential dependency on the parameters and only doubly exponential for every constant t. By this we come very close the known double exponential bound (based on the exponential time hypothesis) that holds already for two-stage stochastic IPs, i.e. multistage stochastic IPs with only two stages. The improved running time of the algorithm is based on new bounds for the proximity of multistage stochastic IPs. The idea behind the bound is based on generalization for a structural lemma originally used for two-stage stochastic IPs. While the structural lemma requires iteration to be applied to multistage stochastic IPs, our generalization directly applies to inherent combinatorial properties of multiple stages. Already a special case of our lemma yields an improved bound for the Graver Complexity of multistage stochastic IPs.

We introduce a very natural generalization of the well-known problem of simultaneous congruences. Instead of searching for a positive integer $s$ that is specified by $n$ fixed remainders modulo integer divisors $a_1,\dots,a_n$ we consider remainder intervals $R_1,\dots,R_n$ such that $s$ is feasible if and only if $s$ is congruent to $r_i$ modulo $a_i$ for some remainder $r_i$ in interval $R_i$ for all $i$. This problem is a special case of a 2-stage integer program with only two variables per constraint which is is closely related to directed Diophantine approximation as well as the mixing set problem. We give a hardness result showing that the problem is NP-hard in general. By investigating the case of harmonic divisors, i.e. $a_{i+1}/a_i$ is an integer for all $i

Abstract We consider so called 2-stage stochastic integer programs (IPs) and their generalized form, so called multi-stage stochastic IPs. A 2-stage stochastic IP is an integer program of the form $$\max \{ c^T x \mid {\mathcal {A}} x = b, \,l \le x \le u,\, x \in {\mathbb {Z}}^{s + nt} \}$$ max { c T x ∣ A x = b , l ≤ x ≤ u , x ∈ Z s + n t } where the constraint matrix $${\mathcal {A}} \in {\mathbb {Z}}^{r n \times s +nt}$$ A ∈ Z r n × s + n t consists roughly of n repetitions of a matrix $$A \in {\mathbb {Z}}^{r \times s}$$ A ∈ Z r × s on the vertical line and n repetitions of a matrix $$B \in {\mathbb {Z}}^{r \times t}$$ B ∈ Z r × t on the diagonal. In this paper we improve upon an algorithmic result by Hemmecke and Schultz from 2003 [Hemmecke and Schultz, Math. Prog. 2003] to solve 2-stage stochastic IPs. The algorithm is based on the Graver augmentation framework where our main contribution is to give an explicit doubly exponential bound on the size of the augmenting steps. The previous bound for the size of the augmenting steps relied on non-constructive finiteness arguments from commutative algebra and therefore only an implicit bound was known that depends on parameters r, s, t and $$\Delta $$ Δ , where $$\Delta $$ Δ is the largest entry of the constraint matrix. Our new improved bound however is obtained by a novel theorem which argues about intersections of paths in a vector space. As a result of our new bound we obtain an algorithm to solve 2-stage stochastic IPs in time $$f(r,s,\Delta ) \cdot \mathrm {poly}(n,t)$$ f ( r , s , Δ ) · poly ( n , t ) , where f is a doubly exponential function. To complement our result, we also prove a doubly exponential lower bound for the size of the augmenting steps.

Integer linear programs of configurations, or configuration IPs, are a classical tool in the design of algorithms for scheduling and packing problems, where a set of items has to be placed in multiple target locations. Herein a configuration describes a possible placement on one of the target locations, and the IP is used to chose suitable configurations covering the items. We give an augmented IP formulation, which we call the module configuration IP. It can be described within the framework of n-fold integer programming and therefore be solved efficiently. As an application, we consider scheduling problems with setup times, in which a set of jobs has to be scheduled on a set of identical machines, with the objective of minimizing the makespan. For instance, we investigate the case that jobs can be split and scheduled on multiple machines. However, before a part of a job can be processed an uninterrupted setup depending on the job has to be paid. For both of the variants that jobs can be executed in parallel or not, we obtain an efficient polynomial time approximation scheme (EPTAS) of running time $f(1/\varepsilon)\times \mathrm{poly}(|I|)$ with a single exponential term in $f$ for the first and a double exponential one for the second case. Previously, only constant factor approximations of $5/3$ and $4/3 + \varepsilon$ respectively were known. Furthermore, we present an EPTAS for a problem where classes of (non-splittable) jobs are given, and a setup has to be paid for each class of jobs being executed on one machine.

Machine scheduling is a fundamental optimization problem in computer science. The task of scheduling a set of jobs on a given number of machines and minimizing the makespan is well studied and among other results, we know that EPTAS's for machine scheduling on identical machines exist. Das and Wiese initiated the research on a generalization of makespan minimization, that includes so called bag-constraints. In this variation of machine scheduling the given set of jobs is partitioned into subsets, so called bags. Given this partition a schedule is only considered feasible when on any machine there is at most one job from each bag. Das and Wiese showed that this variant of machine scheduling admits a PTAS. We will improve on this result by giving the first EPTAS for the machine scheduling problem with bag-constraints. We achieve this result by using new insights on this problem and restrictions given by the bag-constraints. We show that, to gain an approximate solution, we can relax the bag-constraints and ignore some of the restrictions. Our EPTAS uses a new instance transformation that will allow us to schedule large and small jobs independently of each other for a majority of bags. We also show that it is sufficient to respect the bag-constraint only among a constant number of bags, when scheduling large jobs. With these observations our algorithm will allow for some conflicts when computing a schedule and we show how to repair the schedule in polynomial-time by swapping certain jobs around.

In this paper we develop new techniques for covering linear programs and covering integer linear programs to find an approximate solution with improved objective value close to an existing solution. The task of improving an approximate solution is closely related to a classical theorem of Cook et al. [ Math. Programming, 34 (1986), pp. 251--264] in the sensitivity analysis for linear programs and integer linear programs. This result is often applied in the design of robust algorithms for online problems. We apply our new techniques to the online bin packing problem, where it is allowed to reassign already packed items. The migration factor measures the amount of repacked items. It is defined by the total size of reassigned items divided by the size of the arriving item. We obtain a robust asymptotic fully polynomial time approximation scheme (AFPTAS) for the online bin packing problem with migration factor bounded by a polynomial in $\frac{1}{\epsilon}$. To the best of our knowledge, this is the first (asymptotic) PTAS with polynomial migration for an NP-hard problem. As a byproduct we prove an approximate variant of the sensitivity theorem by Cook et al. [ Math. Programming, 34 (1986), pp. 251--264] for linear programs.

We consider integer programming problems max {c^Tx : A x = b, l <= x <= u, x in Z^{nt}} where A has a (recursive) block-structure generalizing n-fold integer programs which recently received considerable attention in the literature. An n-fold IP is an integer program where A consists of n repetitions of submatrices A in Z^{r × t} on the top horizontal part and n repetitions of a matrix B in Z^{s × t} on the diagonal below the top part. Instead of allowing only two types of block matrices, one for the horizontal line and one for the diagonal, we generalize the n-fold setting to allow for arbitrary matrices in every block. We show that such an integer program can be solved in time n^2t^2 phi x (r s delta)^{O(rs^2+ sr^2)} (ignoring logarithmic factors). Here delta is an upper bound on the largest absolute value of an entry of A and phi is the largest binary encoding length of a coefficient of c. This improves upon the previously best algorithm of Hemmecke, Onn and Romanchuk that runs in time n^3t^3 phi x delta^{O(st(r+t))}. In particular, our algorithm is not exponential in the number t of columns of A and B. Our algorithm is based on a new upper bound on the l_1-norm of an element of the Graver basis of an integer matrix and on a proximity bound between the LP and IP optimal solutions tailored for IPs with block structure. These new bounds rely on the Steinitz Lemma. Furthermore, we extend our techniques to the recently introduced tree-fold IPs, where we again present a more efficient algorithm in a generalized setting.

We consider the relaxed online strip packing problem, where rectangular items arrive online and have to be packed into a strip of fixed width such that the packing height is minimized. Thereby, repacking of previously packed items is allowed. The amount of repacking is measured by the migration factor, defined as the total size of repacked items divided by the size of the arriving item. First, we show that no algorithm with constant migration factor can produce solutions with asymptotic ratio better than 4/3. Against this background, we allow amortized migration, i.e. to save migration for a later time step. As a main result, we present an AFPTAS with asymptotic ratio 1 + O(epsilon) for any epsilon > 0 and amortized migration factor polynomial in 1/epsilon. To our best knowledge, this is the first algorithm for online strip packing considered in a repacking model.

We consider the bin packing problem with d different item sizes and revisit the structure theorem given by Goemans and Rothvoß [5] about solutions of the integer cone. We present new techniques on how solutions can be modified and give a new structure theorem that relies on the set of vertices of the underlying integer polytope. As a result of our new structure theorem, we obtain an algorithm for the bin packing problem with running time where V is the set of vertices of the integer knapsack poly- tope and enc(I) is the encoding length of the bin packing instance. The algorithm is fixed parameter tractable, parameterized by the number of vertices of the integer knapsack polytope |V|. This shows that the bin packing problem can be solved efficiently when the underlying integer knapsack polytope has an easy structure, i.e. has a small number of vertices. Furthermore, we show that the presented bounds of the structure theorem are asymptotically tight. We give a construction of bin packing instances using new structural insights and classical number theoretical theorems which yield the desired lower bound.