Andreas Wiese

Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely et al.

The (Non-Preemptive) Throughput Maximization problem is a natural and fundamental scheduling problem. We are given $n$ jobs, where each job $j$ is characterized by a processing time and a time window, contained in a global interval $[0,T)$, during which~$j$ can be scheduled. Our goal is to schedule the maximum possible number of jobs non-preemptively on a single machine, so that no two scheduled jobs are processed at the same time. This problem is known to be strongly NP-hard. The best-known approximation algorithm for it has an approximation ratio of $1/0.6448 + \varepsilon \approx 1.551 + \varepsilon$ [Im, Li, Moseley IPCO'17], improving on an earlier result in [Chuzhoy, Ostrovsky, Rabani FOCS'01]. In this paper we substantially improve the approximation factor for the problem to $4/3+\varepsilon$ for any constant~$\varepsilon>0$. Using pseudo-polynomial time $(nT)^{O(1)}$, we improve the factor even further to $5/4+\varepsilon$. Our results extend to the setting in which we are given an arbitrary number of (identical) machines.

Debajyoti Kar, Arindam Khan, Andreas Wiese

We study the two-dimensional (geometric) knapsack problem with rotations (2DKR), in which we are given a square knapsack and a set of rectangles with associated profits. The objective is to find a maximum profit subset of rectangles that can be packed without overlap in an axis-aligned manner, possibly by rotating some rectangles by $90^{\circ}$. The best-known polynomial time algorithm for the problem has an approximation ratio of $3/2+ε$ for any constant $ε>0$, with an improvement to $4/3+ε$ in the cardinality case, due to G{á}lvez et al. (FOCS 2017, TALG 2021). Obtaining a PTAS for the problem, even in the cardinality case, has remained a major open question in the setting of multidimensional packing problems, as mentioned in the survey by Christensen et al. (Computer Science Review, 2017). In this paper, we present a PTAS for the cardinality case of 2DKR. In contrast to the setting without rotations, we show that there are $(1+ε)$-approximate solutions in which all items are packed greedily inside a constant number of rectangular {\em containers}. Our result is based on a new resource contraction lemma, which might be of independent interest. In contrast, for the general weighted case, we prove that this simple type of packing is not sufficient to obtain a better approximation ratio than $1.5$. However, we break this structural barrier and design a $(1.497+ε)$-approximation algorithm for 2DKR in the weighted case. Our arguments also improve the best-known approximation ratio for the (weighted) case {\em without rotations} to $13/7+ε\approx 1.857+ε$. Finally, we establish a lower bound of $n^{Ω(1/ε)}$ on the running time of any $(1+ε)$-approximation algorithm for our problem with or without rotations -- even in the cardinality setting, assuming the $k$-\textsc{Sum} Conjecture.

Debajyoti Kar, Arindam Khan, Andreas Wiese

We study ROUND-UFP and ROUND-SAP, two generalizations of the classical BIN PACKING problem that correspond to the unsplittable flow problem on a path (UFP) and the storage allocation problem (SAP), respectively. We are given a path with capacities on its edges and a set of tasks where for each task we are given a demand and a subpath. In ROUND-UFP, the goal is to find a packing of all tasks into a minimum number of copies (rounds) of the given path such that for each copy, the total demand of tasks on any edge does not exceed the capacity of the respective edge. In ROUND-SAP, the tasks are considered to be rectangles and the goal is to find a non-overlapping packing of these rectangles into a minimum number of rounds such that all rectangles lie completely below the capacity profile of the edges. We show that in contrast to BIN PACKING, both the problems do not admit an asymptotic polynomial-time approximation scheme (APTAS), even when all edge capacities are equal. However, for this setting, we obtain asymptotic $(2+\varepsilon)$-approximations for both problems. For the general case, we obtain an $O(\log\log n)$-approximation algorithm and an $O(\log\log\frac{1}δ)$-approximation under $(1+δ)$-resource augmentation for both problems. For the intermediate setting of the no bottleneck assumption (i.e., the maximum task demand is at most the minimum edge capacity), we obtain absolute $12$- and asymptotic $(16+\varepsilon)$-approximation algorithms for ROUND-UFP and ROUND-SAP, respectively.