Consider a high-multiplicity Bin Packing instance $I$ with $d$ distinct item types. In 2014, Goemans and Rothvoss gave an algorithm with runtime ${{|I|}^2}^{O(d)}$ for this problem~[SODA'14], where $|I|$ denotes the encoding length of the instance $I$. Although Jansen and Klein~[SODA'17] later developed an algorithm that improves upon this runtime in a special case, it has remained a major open problem by Goemans and Rothvoss~[J.ACM'20] whether the doubly exponential dependency on $d$ is necessary. We solve this open problem by showing that unless the ETH fails, there is no algorithm solving the high-multiplicity Bin Packing problem in time ${{|I|}^2}^{o(d)}$. To prove this, we introduce a novel reduction from 3-SAT. The core of our construction is efficiently encoding all information from a 3-SAT instance with $n$ variables into an ILP with $O(\log(n))$ variables and constraints. This result confirms that the Goemans and Rothvoss algorithm is essentially best-possible for Bin Packing parameterized by the number $d$ of item sizes in the context of XP time algorithms.

In the problem of Parallel Task Scheduling (PTS), we are asked to schedule n jobs, each with a fixed processing time and machine requirement, such that the completion time of the last job is minimized. Jansen and Rau (2019) presented an algorithm for PTS that achieves an approximation ratio of (3/2)OPT + pmax. They additionally posed the open question whether an approximation ratio of (4/3)OPT + pmax is possible. In this work, we present such an algorithm with a running time of O(n log n).

We present an efficient polynomial-time approximation scheme (EPTAS) for the problem of scheduling jobs on parallel uniform machines that improves all previously known EPTAS for the problem. Our algorithm uses a Mixed Integer Linear Program (MILP) formulation for a relaxed version of the problem. We simplify the MILP by repeatedly removing carefully selected sets of jobs and machines until all integer variables have been removed. Then, we build up the solution through the use of a dynamic programming approach, enumeration, and linear program solving. Notable about our approach is that our algorithm only uses an LP solver, different from previous EPTAS approaches where MILP solvers are necessary.

Solving a general integer program (IP) is NP-hard. The classic algorithm [Papadimitriou, J.ACM '81] for IPs has a running time n^{{𝒪}(m)}(m⋅max{Δ,‖b‖_{∞}})^{{𝒪}(m²)}, where m is the number of constraints, n is the number of variables, and Δ and ‖b‖_{∞} are, respectively, the largest absolute values among the entries in the constraint matrix and the right-hand side vector of the constraint. The running time is exponential in m, and becomes pseudo-polynomial if m is a constant. In recent years, there has been extensive research on FPT (fixed parameter tractable) algorithms for the so-called n-fold IPs, which may possess a large number of constraints, but the constraint matrix satisfies a specific block structure. It is remarkable that these FPT algorithms take as parameters Δ and the number of rows and columns of some small submatrices. If Δ is not treated as a parameter, then the running time becomes pseudo-polynomial even if all the other parameters are taken as constants. This paper explores the trade-off between time and accuracy in solving an IP. We show that, for arbitrary small ε > 0, there exists an algorithm for IPs with m constraints that runs in {f(m,ε)}⋅poly(|I|) time, and returns a near-feasible solution that violates the constraints by at most εΔ. Furthermore, for n-fold IPs, we establish a similar result - our algorithm runs in time that depends on the number of rows and columns of small submatrices together with 1/ε, and returns a solution that slightly violates the constraints. Meanwhile, both solutions guarantee that their objective values are no worse than the corresponding optimal objective values satisfying the constraints. As applications, our results can be used to obtain additive approximation schemes for multidimensional knapsack as well as scheduling.

In moldable job scheduling, we are provided m identical machines and n jobs that can be executed on a variable number of machines. The execution time of each job depends on the number of machines assigned to execute that job. For the specific problem of monotone moldable job scheduling, jobs are assumed to have a processing time that is non-increasing in the number of machines. The previous best-known algorithms are: (1) a Polynomial Time Approximation Scheme (PTAS) with time complexity Ω(n^{g(1/ε)}), where g(⋅) is a super-exponential function [Jansen and Thöle '08; Jansen and Land '18], (2) a Fully Polynomial Time Approximation Scheme (FPTAS) for the case of m ≥ 8n/(ε) [Jansen and Land '18], and (3) a 3/2 approximation with time complexity O(nmlog(mn)) [Wu, Zhang, and Chen '23]. We present a new practically efficient algorithm with an approximation ratio of ≈ (1.4593 + ε) and a time complexity of O(nm log 1/(ε)). Our result also applies to the contiguous variant of the problem. In addition to our theoretical results, we implement the presented algorithm and show that the practical performance is significantly better than the theoretical worst-case approximation ratio.

Block-structured integer linear programs (ILPs) play an important role in various application fields. We address n-fold ILPs where the matrix 𝒜 has a specific structure, i.e., where the blocks in the lower part of 𝒜 consist only of the row vectors (1,… ,1). In this paper, we propose an approach tailored to exactly these combinatorial n-folds. We utilize a divide and conquer approach to separate the original problem such that the right-hand side iteratively decreases in size. We show that this decrease in size can be calculated such that we only need to consider a bounded amount of possible right-hand sides. This, in turn, lets us efficiently combine solutions of the smaller right-hand sides to solve the original problem. We can decide the feasibility of, and also optimally solve, such problems in time (n r Δ)^O(r) log(‖b‖_∞), where n is the number of blocks, r the number of rows in the upper blocks and Δ = ‖A‖_∞. We complement the algorithm by discussing applications of the n-fold ILPs with the specific structure we require. We consider the problems of (i) scheduling on uniform machines, (ii) closest string and (iii) (graph) imbalance. Regarding (i), our algorithm results in running times of p_max^O(d)|I|^O(1), matching a lower bound derived via ETH. For (ii) we achieve running times matching the current state-of-the-art in the general case. In contrast to the state-of-the-art, our result can leverage a bounded number of column-types to yield an improved running time. For (iii), we improve the parameter dependency on the size of the vertex cover.

In the Knapsack problem, one is given the task of packing a knapsack of a given size with items in order to gain a packing with a high profit value. As one of the most classical problems in computer science, research for this problem has gone a long way. One important connection to the (max,+)-convolution problem has been established, where knapsack solutions can be combined by building the convolution of two sequences. This observation has been used in recent years to give conditional lower bounds but also parameterized algorithms. In this paper we carry these results into higher dimensions. We consider Knapsack where items are characterized by multiple properties - given through a vector - and a knapsack that has a capacity vector. The packing must not exceed any of the given capacity constraints. In order to show a similar sub-quadratic lower bound we consider a multidimensional version of (max, +)-convolution. We then consider variants of this problem introduced by Cygan et al. and prove that they are all equivalent in terms of algorithms that allow for a running time sub-quadratic in the number of entries of the array. We further develop a parameterized algorithm to solve higher dimensional Knapsack. The techniques we apply are inspired by an algorithm introduced by Axiotis and Tzamos. We will show that even for higher dimensional Knapsack, we can reduce the problem to convolution on one-dimensional, concave sequences, leading to an 𝒪(dn + dD ⋅ max{(Π_{i=1}^d t_i), t_max log t_max}) algorithm, where D is the number of different weight vectors, t the capacity vector and d is the dimension of the problem. Then, we use the techniques to improve the approach of Eisenbrand and Weismantel to obtain an algorithm for Integer Linear Programming with upper bounds with running time 𝒪(dn) + D ⋅ 𝒪(d Δ)^{d(d+1)} + T_LP. Finally, we give an divide-and-conquer algorithm for ILP with running time n^{d+1} ⋅ O(Δ)^d ⋅ log(|u - 𝓁|_∞).

We settle the pseudo-polynomial complexity of the Demand Strip Packing (DSP) problem: Given a strip of fixed width and a set of items with widths and heights, the items must be placed inside the strip with the objective of minimizing the peak height. This problem has gained significant scientific interest due to its relevance in smart grids~[Deppert~et~al. APPROX'21, Gálvez~et~al. APPROX'21]. Smart Grids are a modern form of electrical grid that provide opportunities for optimization. They are forecast to impact the future of energy provision significantly. Algorithms running in pseudo-polynomial time lend themselves to these applications as considered time intervals, such as days, are small. Moreover, such algorithms can provide superior approximation guarantees over those running in polynomial time. Consequently, they evoke scientific interest in related problems~[Jansen and Rau ESA'19]. We prove that Demand Strip Packing is strongly NP-hard for approximation ratios below~5/4. Through this proof, we provide novel insights into the relation of packing and scheduling problems. Using these insights, we show a series of frameworks that solve both Demand Strip Packing and Parallel Task Scheduling optimally when increasing the strip's width or number of machines. Such alterations to problems are known as resource augmentation. Applications are found when penalty costs are prohibitively large. Finally, we provide a pseudo-polynomial time approximation algorithm for DSP with an approximation ratio of (5/4+ε), which is nearly optimal assuming P≠neq NP. The construction of this algorithm provides several insights into the structure of DSP solutions and uses novel techniques to restructure optimal solutions.

We present a fast and efficient 3/2 dual approximation algorithm for CPU/GPU scheduling under the objective of makespan minimization. In CPU/GPU scheduling tasks can be scheduled on two different architectures. When executed on the CPU, a task is moldable and can be assigned to multiple cores. The running time becomes a function in the assigned cores. On a GPU, the task is a classical job with a set processing time. Both settings have drawn recent independent scientific interest. For the moldable CPU scheduling, the current best known constant rate approximation is a 3/2 approximation algorithm [Wu et al. EJOR volume 306]. The best efficient algorithm for this setting is a 3/2+ε approximation [Mounie et al. SIAM '07] whereas GPU scheduling admits a 13/11 approximation [Coffman, Garey, Johnson SIAM'78]. We improve upon the current best known algorithms for CPU/GPU scheduling by Bleuse et al. by formulating a novel multidimensional multiple choice knapsack to allot tasks to either architecture and schedule them there with known algorithms. This yields an improved running time over the current state of the art. We complement our theoretical results with experimentation that shows a significant speedup by using practical optimizations and explore their efficacy.

Consider the many shared resources scheduling problem where jobs have to be scheduled on identical parallel machines with the goal of minimizing the makespan. However, each job needs exactly one additional shared resource in order to be executed and hence prevents the execution of jobs that need the same resource while being processed. Previously, an approximation ratio of asymptotically 2 was the best known result for this problem. Furthermore, a 6/5-approximation for the case with only two machines was known as well as a PTAS for the case with a constant number of machines. We present a simple and fast 5/3-approximation and a much more involved but still reasonable 1.5-approximation. Furthermore, we provide a PTAS for the case with only a constant number of machines, which is arguably simpler and faster than the previously known one, as well as a PTAS with resource augmentation for the general case. The approximation schemes make use of the N-fold integer programming machinery, which has found more and more applications in the field of scheduling recently. It is plausible that the latter results can be improved and extended to more general cases. Lastly, we give an inapproximability result for the natural problem extension where each job may need up to a constant number of different resources, namely 3, ruling out better than 5/4 approximations for that case.

Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows that any feasible integer linear program (ILP) has a solution with support size $s\leq 2m\cdot\log(4mΔ)$, where $m$ is the number of constraints, and $Δ$ is the largest coefficient in any constraint. Our main combinatorial result are improved support size bounds for ILPs. To improve granularity, we analyze for the largest $1$-norm $A_{\max}$ of any column of the constraint matrix, instead of $Δ$. We show a support size upper bound of $s\leq m\cdot(\log(3A_{\max})+\sqrt{\log(A_{\max})})$, by deriving a new bound on the -1 branch of the Lambert $\mathcal{W}$ function. Additionally, we provide a lower bound of $m\log(A_{\max})$, proving our result asymptotically optimal. Furthermore, we give support bounds of the form $s\leq 2m\cdot\log(1.46A_{\max})$. These improve upon the previously best constants by Aliev. et. al. (SIAM J. Optim., 2018), because all our upper bounds hold equally with $A_{\max}$ replaced by $\sqrt{m}Δ$. Using our combinatorial result, we obtain the fastest known approximation schemes (EPTAS) for the fundamental scheduling problem of makespan minimization of uniformly related machines ($Q\mid\mid C_{\max}$).

Abstract We study the Non-preemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Non-preemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a $$(5/3+\varepsilon )$$ (5/3+ε) -approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption $$(1+\varepsilon ) {\textrm{OPT}}$$ (1+ε)OPT . The remaining jobs fit into a thin container of height 1. This AEPTAS is used as a subroutine to acquire the $$(5/3+\varepsilon )$$ (5/3+ε) -approximation algorithm. The previous best result for NPDM was a 2.7-approximation based on FFDH (Ranjan et al., in: 2015 IEEE symposium on computers and communication (ISCC), pp 758–763, IEEE, 2015). One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg’s algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above, such that it does not exceed the bound of $$(5/3+\varepsilon ) {\textrm{OPT}}$$ (5/3+ε)OPT .

Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. A well-studied measure of the amount of decisions that can be revoked is the (constant) migration factor. When an object arrives, the decisions for objects of total size at most the migration factor times its size may be revoked. This means that a small object only leads to small changes. We extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case where only insertions are allowed, and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worst-case migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio. We therefore resolve the competitiveness of the bin covering problem with migration.

There is a long history of approximation schemes for the problem of scheduling jobs on identical machines to minimize the makespan. Such a scheme grants a (1 + ε)-approximation solution for every ε > 0, but the running time grows exponentially in 1/ε. For a long time, these schemes seemed like a purely theoretical concept. Even solving instances for moderate values of ε seemed completely illusional. In an effort to bridge theory and practice, we refine recent ILP techniques to develop the fastest known approximation scheme for this problem. An implementation of this algorithm reaches values of ε lower than 2/11 ≈ 18.2% within a reasonable timespan. This is the approximation guarantee of MULTIFIT, which, to the best of our knowledge, has the best proven guarantee of any non-scheme algorithm.

We study the d-dimensional hypercube knapsack problem where we are given a set of d-dimensional hypercubes with associated profits, and a knapsack which is a unit d-dimensional hypercube. The goal is to find an axis-aligned non-overlapping packing of a subset of hypercubes such that the profit of the packed hypercubes is maximized. For this problem, Harren (ICALP'06) gave an algorithm with an approximation ratio of (1+1/2^d+epsilon). For d=2, Jansen and Solis-Oba (IPCO'08) showed that the problem admits a polynomial-time approximation scheme (PTAS); Heydrich and Wiese (SODA'17) further improved the running time and gave an efficient polynomial-time approximation scheme (EPTAS). Both the results use structural properties of 2-D packing, which do not generalize to higher dimensions. For d>2, it remains open to obtain a PTAS, and in fact, there has been no improvement since Harren's result. We settle the problem by providing a PTAS. Our main technical contribution is a structural lemma which shows that any packing of hypercubes can be converted into another structured packing such that a high profitable subset of hypercubes is packed into a constant number of special hypercuboids, called V-Boxes and N-Boxes. As a side result, we give an almost optimal algorithm for a variant of the strip packing problem in higher dimensions. This might have applications for other multidimensional geometric packing problems.

We study the Nonpreemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Nonpreemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a (5/3+ε)-approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption (1+ε) OPT. The remaining jobs fit into a thin container of height 1. The previous best result for NPDM was a 2.7 approximation based on FFDH [Ranjan et al., 2015]. One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg’s algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above.

In the problem called single resource constraint scheduling, we are given m identical machines and a set of jobs, each needing one machine to be processed as well as a share of a limited renewable resource R. A schedule of these jobs is feasible if, at each point in the schedule, the number of machines and resources required by jobs processed at this time is not exceeded. It is NP-hard to approximate this problem with a ratio better than 3/2. On the other hand, the best algorithm so far has an absolute approximation ratio of 2+ε. In this paper, we present an algorithm with absolute approximation ratio (3/2+ε), which closes the gap between inapproximability and best algorithm with exception of a negligible small ε.

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

In the Strip Packing problem, we are given a vertical half-strip [0,W]× [0,+∞) and a collection of open rectangles of width at most W. Our goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip such that the maximum height OPT spanned by the packing is as small as possible. Strip Packing generalizes classical well-studied problems such as Makespan Minimization on identical machines (when rectangle widths are identical) and Bin Packing (when rectangle heights are identical). It has applications in manufacturing, scheduling and energy consumption in smart grids among others. It is NP-hard to approximate this problem within a factor (3/2-ε) for any constant ε > 0 by a simple reduction from the Partition problem. The current best approximation factor for Strip Packing is (5/3+ε) by Harren et al. [Computational Geometry '14], and it is achieved with a fairly complex algorithm and analysis. It seems plausible that Strip Packing admits a (3/2+ε)-approximation. We make progress in that direction by achieving such tight approximation guarantees for a special family of instances, which we call skewed instances. As standard in the area, for a given constant parameter δ > 0, we call large the rectangles with width at least δ W and height at least δ OPT, and skewed the remaining rectangles. If all the rectangles in the input are large, then one can easily compute the optimal packing in polynomial time (since the input can contain only a constant number of rectangles). We consider the complementary case where all the rectangles are skewed. This second case retains a large part of the complexity of the original problem; in particular, it is NP-hard to approximate within a factor (3/2-ε) and we provide an (almost) tight (3/2+ε)-approximation algorithm.

Assigning jobs onto identical machines with the objective to minimize the maximal load is one of the most basic problems in combinatorial optimization and has many practical applications in manufacturing, parallel computation, service industries among others. Motivated by its utilization in product planing and data placement we study a natural extension called Class Constrained Scheduling (CCS). In this problem each job additionally admits a class and each machine can only schedule jobs from at most c different classes for some number c. Even though this problem is closely related to the Class Constraint Bin Packing, the Class Constraint Knapsack and the Cardinality Constraint variants, CCS lacks results regarding approximation algorithms despite being also NP-hard. We fill this gap by analyzing the problem considering three different ways to feasibly allot the jobs: The non-preemptive case, where we have to place the jobs as a whole; the splittable case, where we are allowed to split and allot the jobs arbitrarily as long as they do not overlap on a machine; and finally the preemptive case, where jobs can be split but pieces belonging to the same job are not allowed to be scheduled in parallel. For each case we introduce the first PTAS where neither c nor the number of all classes have to be a constant. In order to achieve this goal, we give new insights about the structure of optimal solutions. In particular we prove that there always exists an optimal solution where the jobs are split evenly and the number of pieces for each job is bounded. Further these job pieces will be placed in just a few specific positions. Moreover, by preprocessing the instance appropriately, we manage to set up a configuration Integer Linear Program (ILP) with a specific form of the constraint matrix called N-fold ILP. These N-fold ILPs can then be solved efficiently. Additionally, we developed the first simple approximation algorithms with constant approximation ratios running in more efficient, polynomial time. The algorithm for the non-preemptive case has a ratio of 7/3 and a running time of O(n2 log(n) + n log2(pmax)). The splittable and the preemptive case admit algorithms with ratio~2 and a running time of O(n2 log(n)). All results also hold when the number of machines cannot be bounded by a polynomial in n.

In the restricted assignment problem, the input consists of a set of machines and a set of jobs each with a processing time and a subset of eligible machines. The goal is to find an assignment of the jobs to the machines minimizing the makespan, that is, the maximum summed up processing time any machine receives. Herein, jobs should only be assigned to those machines on which they are eligible. It is well-known that there is no polynomial time approximation algorithm with an approximation guarantee of less than 1.5 for the restricted assignment problem unless P=NP. In this work, we show hardness results for variants of the restricted assignment problem with particular types of restrictions. In the case of interval restrictions the machines can be totally ordered such that jobs are eligible on consecutive machines. We resolve the open question of whether the problem admits a polynomial time approximation scheme (PTAS) in the negative (unless P=NP). There are several special cases of this problem known to admit a PTAS. Furthermore, we consider a variant with resource restriction where each machine has capacities and each job demands for a fixed number of resources. A job is eligible on a machine if its demand is at most the capacity of the machine for each resource. For one resource, this problem is known to admit a PTAS, for two, the case of interval restrictions is contained, and in general, the problem is closely related to unrelated scheduling with a low rank processing time matrix. We show that there is no polynomial time approximation algorithm with a rate smaller than 48/47 or 1.5 for scheduling with resource restrictions with 2 or 4 resources, respectively, unless P=NP. All our results can be extended to the so called Santa Claus variants of the problems where the goal is to maximize the minimal processing time any machine receives.

The Restricted Assignment problem is a prominent special case of Scheduling on Unrelated Parallel Machines. For the strongest known linear programming relaxation, the configuration LP, we improve the nonconstructive bound on its integrality gap from 1.9412 to 1.8334 and significantly simplify the proof. Then we give a constructive variant, yielding a 1.8334-approximation in quasi-polynomial time. This is the first quasi-polynomial algorithm for this problem improving on the long-standing approximation rate of 2.

We study an important case of integer linear programs (ILPs) of the form $\max\{c^Tx \ \vert\ \mathcal Ax = b, l \leq x \leq u,\, x \in \mathbb{Z}^{n t} \} $ with $n t$ variables and lower and upper bounds $\ell, u\in\mathbb Z^{nt}$. In $n$-fold ILPs nonzero entries only appear in the first $r$ rows of the matrix $\mathcal A$ and in small blocks of size $s\times t$ along the diagonal underneath. Despite this restriction, many optimization problems can be expressed in this form. It is known that $n$-fold ILPs are fixed-parameter tractable (FPT) regarding the parameters $s, r,$ and $\Delta$, where $\Delta$ is the greatest absolute value of any entry in $\mathcal A$. The state-of-the-art technique is a local search algorithm that subsequently moves in an improving direction where the number of iterations and the search for such an improving direction each take time $\Omega(n)$. This leads to a running time quadratic in $n$. We introduce a technique based on color coding which allows us to compute these improving directions in logarithmic time after a single initialization step. This yields an algorithm for $n$-fold ILPs with a running time that is near-linear in $nt$, the number of variables. More precisely, our algorithm runs in time $(rs\Delta)^{\mathcal{O}(r^2s + s^2)} L^2 nt \log^{\mathcal{O}(1)}(nt)$, where $L$ is the encoding length of the largest integer in the input. Further, in contrast to the algorithms in recent literature, we do not need to solve the LP relaxation in order to handle unbounded variables. Instead we give a structural lemma to introduce appropriate bounds. On the other hand, if we are given such an LP solution, the running time can be decreased by a factor of $L$.

The set of 2-dimensional packing problems builds an important class of optimization problems and Strip Packing together with 2-dimensional Bin Packing and 2-dimensional Knapsack is one of the most famous of these problems. Given a set of rectangular axis parallel items and a strip with bounded width and infinite height the objective is to find a packing of the items into the strip which minimizes the packing height. We speak of pseudo-polynomial Strip Packing if we consider algorithms with pseudo-polynomial running time with respect to the width of the strip. It is known that there is no pseudo-polynomial algorithm for Strip Packing with a ratio better than $5/4$ unless $\mathrm{P} = \mathrm{NP}$. The best algorithm so far has a ratio of $(4/3 + \varepsilon)$. In this paper, we close this gap between inapproximability result and best known algorithm by presenting an algorithm with approximation ratio $(5/4 + \varepsilon)$ and thus categorize the problem accurately. The algorithm uses a structural result which states that each optimal solution can be transformed such that it has one of a polynomial number of different forms. The strength of this structural result is that it applies to other problem settings as well for example to Strip Packing with rotations (90 degrees) and Contiguous Moldable Task Scheduling. This fact enabled us to present algorithms with approximation ratio $(5/4 + \varepsilon)$ for these problems as well.

Graph Balancing is the problem of orienting the edges of a weighted multigraph so as to minimize the maximum weighted in-degree. Since the introduction of the problem the best algorithm known achieves an approximation ratio of $1.75$ and it is based on rounding a linear program with this exact integrality gap. It is also known that there is no $(1.5 - ε)$-approximation algorithm, unless $\mathrm{P}=\mathrm{NP}$. Can we do better than $1.75$? We prove that a different LP formulation, the configuration LP, has a strictly smaller integrality gap. Graph Balancing was the last one in a group of related problems from literature, for which it was open whether the configuration LP is stronger than previous, simple LP relaxations. We base our proof on a local search approach that has been applied successfully to the more general Restricted Assignment problem, which in turn is a prominent special case of makespan minimization on unrelated machines. With a number of technical novelties we are able to obtain a bound of $1.749$ for the case of Graph Balancing. It is not clear whether the local search algorithm we present terminates in polynomial time, which means that the bound is non-constructive. However, it is a strong evidence that a better approximation algorithm is possible using the configuration LP and it allows the optimum to be estimated within a factor better than $1.75$. A particularly interesting aspect of our techniques is the way we handle small edges in the local search. We manage to exploit the configuration constraints enforced on small edges in the LP. This may be of interest to other problems such as Restricted Assignment as well.

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.

Integer programs with a constant number of constraints are solvable in pseudo-polynomial time. We give a new algorithm with a better pseudo-polynomial running time than previous results. Moreover, we establish a strong connection to the problem (min, +)-convolution. (min, +)-convolution has a trivial quadratic time algorithm and it has been conjectured that this cannot be improved significantly. We show that further improvements to our pseudo-polynomial algorithm for any fixed number of constraints are equivalent to improvements for (min, +)-convolution. This is a strong evidence that our algorithm's running time is the best possible. We also present a faster specialized algorithm for testing feasibility of an integer program with few constraints and for this we also give a tight lower bound, which is based on the SETH.

We consider a natural generalization of scheduling n jobs on m parallel machines so as to minimize the makespan. In our extension the set of jobs is partitioned into several classes and a machine requires a setup whenever it switches from processing jobs of one class to jobs of a different class. During such a setup, a machine cannot process jobs and the duration of a setup may depend on the machine as well as the class of the job to be processed next. For this problem, we study approximation algorithms for nonidentical machines. We develop a polynomial-time approximation scheme for uniformly related machines. For unrelated machines we obtain an O(log n + log m)-approximation, which we show to be optimal (up to constant factors) unless NP ⊂ RP. We also identify two special cases that admit constant factor approximations.

We investigate the scheduling of n jobs divided into c classes on m identical parallel machines. For every class there is a setup time which is required whenever a machine switches from the processing of one class to another class. The objective is to find a schedule that minimizes the makespan. We give near-linear approximation algorithms for the following problem variants: the non-preemptive context where jobs may not be preempted, the preemptive context where jobs may be preempted but not parallelized, as well as the splittable context where jobs may be preempted and parallelized. We present the first algorithm improving the previously best approximation ratio of 2 to a better ratio of 3/2 in the preemptive case. In more detail, for all three flavors we present an approximation ratio 2 with running time O(n), ratio 3/2+ε in time O(nłog 1/ε) as well as a ratio of 3/2. The (3/2)-approximate algorithms have different running times. In the non-preemptive case we get time O(nłog (n+Δ)) where Δ is the largest value of the input. The splittable approximation runs in time O(n+cłog(c+m)) whereas the preemptive algorithm has a running time O(n łog (c+m)) łeq O(n łog n). So far, no PTAS is known for the preemptive problem without restrictions, so we make progress towards that question. Recently Jansen et al. found an EPTAS for the splittable and non-preemptive case but with impractical running times exponential in 1/ε.

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 two related scheduling problems: single resource-constrained scheduling on identical parallel machines and a generalization with resource-dependent processing times. In both problems, jobs require a certain amount of an additional resource and have to be scheduled on machines minimizing the makespan, while at every point in time a given resource capacity is not exceeded. In the first variant of the problem, the processing times and resource amounts are fixed, while in the second the former depends on the latter. Both problems contain bin packing with cardinality constraint as a special case, and, therefore, these problems are strongly NP-complete even for a constant number of machines larger than three, which can be proven by a reduction from 3-Partition. Furthermore, if the number of machines is part of the input, then we cannot hope for an approximation algorithm with absolute approximation ratio smaller than 3/2. We present asymptotic fully polynomial time approximation schemes (AFPTAS) for the problems: For any ε > 0, a schedule of length at most (1+ε) times the optimum plus an additive term of O ( p max log (1/ε)/ε) is provided, and the running time is polynomially bounded in 1/ε and the input length. Up to now, only approximation algorithms with absolute approximation ratios were known. Furthermore, the AFPTAS for resource-constrained scheduling on identical parallel machines directly improves the additive term of the best AFPTAS for bin packing with cardinality constraint so far.

A moldable job is a job that can be executed on an arbitrary number of processors, and whose processing time depends on the number of processors allotted to it. A moldable job is monotone if its work doesn't decrease for an increasing number of allotted processors. We consider the problem of scheduling monotone moldable jobs to minimize the makespan. We argue that for certain compact input encodings a polynomial algorithm has a running time polynomial in n and log m, where n is the number of jobs and m is the number of machines. We describe how monotony of jobs can be used to counteract the increased problem complexity that arises from compact encodings, and give tight bounds on the approximability of the problem with compact encoding: it is NP-hard to solve optimally, but admits a PTAS. The main focus of this work are efficient approximation algorithms. We describe different techniques to exploit the monotony of the jobs for better running times, and present a (3/2 + ε)-approximate algorithm whose running time is polynomial in log m and ε/1, and only linear in the number n of jobs.

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.

We consider the classical problem of scheduling on unrelated machines. In this problem a set of jobs is to be distributed among a set of machines and the maximum load (makespan) is to be minimized. The processing time pij of a job j depends on the machine i it is assigned to. Lenstra, Shmoys and Tardos gave a polynomial time 2-approximation for this problem [8]. In this paper we focus on a prominent special case, the restricted assignment problem, in which pij ∊ {pj, ∞}. The configuration-LP is a linear programming relaxation for the restricted assignment problem. It was shown by Svensson that the multiplicative gap between integral and fractional solution, the integrality gap, is at most 2 – 1/17 ≈ 1.9412 [11]. In this paper we significantly simplify his proof and achieve a bound of 2 – 1/6 ≈ 1.8333. As a direct consequence this provides a polynomial (2 – 1/6 + ∊)-estimation algorithm for the restricted assignment problem by approximating the configuration-LP. The best lower bound known for the integrality gap is 1.5 and no estimation algorithm with a guarantee better than 1.5 exists unless P = NP.

We consider two related scheduling problems: resource constrained scheduling on identical parallel machines and a generalization with resource dependent processing times. In both problems, jobs require a certain amount of an additional resource and have to be scheduled on machines minimizing the makespan, while at every point in time a given resource capacity is not exceeded. In the first variant of the problem the processing times and resource amounts are fixed, while in the second the former depends on the latter. We present asymptotic fully polynomial approximation schemes (AFPTAS) for the problems: For any ∊ > 0 a schedule of length at most (1 + ∊) times the optimum plus an additive term of ℴ(1/∊2) is provided, and the running time is polynomially bounded in 1/∊ and the input length. Up to now only approximation algorithms with constant approximation ratios were known.

Our goal is to show tight bounds on the running time of algorithms for scheduling and packing problems. To prove lower bounds, we investigate implications of the exponential time hypothesis on such algorithms. For exact algorithms we consider the dependence of the running time on the number $n$ of items (for packing) or jobs (for scheduling). We prove a lower bound of $2^{{\rm o}(n)} \times \|{I}\|^{{{\rm O}(n)}}$, where $\|{I}\|$ denotes the encoding length of the instance, for several of these problems, including SubsetSum, Knapsack, BinPacking, $\langle{P2}\|{C_{\max}}\rangle,\ \text{and}\ \langle{P2}\|{\sum w_j C_j}\rangle$. We also develop an algorithmic framework that is able to solve a large number of scheduling and packing problems in time $2^{{\rm o}(n)} \times \|{I}\|^{{{\rm O}(n)}}$. Finally, we consider approximation schemes. We show that there is no polynomial time approximation scheme for MultipleKnapsack (MKS) and 2d-Knapsack with running time $2^{{\rm o}(1/\epsilon)} \times \|{I}\|^{{{\rm O}(n)}}$ and $n^{{\rm o}(1/\epsilon)} \times \|{I}\|^{{{\rm O}(n)}}$, respectively.

We present heuristics to handle practical travelling salesman problems with multiple time windows per node, where the optimization goal is minimal tour duration, which is the time spent outside the depot node. We propose a dynamic programming approach which combines state labels by encoding intervals to handle the larger state space needed for this objective function. Our implementation is able to solve many practical instances in real-time and is used for heuristic search of near-optimal solutions for hard instances. In addition, we outline a hybrid genetic algorithm we implemented to cope with hard or unknown instances. Experimental evaluation proves the efficiency and suitability for practical use of our algorithms and even leads to improved upper bounds for yet unsolved instances from the literature.

We consider the classical scheduling problem on parallel identical machines to minimize the makespan. There is a long history of studies on this problem, focusing on exact and approximation algorithms, and it is thus natural to consider whether these algorithms are best possible in terms of the running time. Under the Exponential Time Hypothesis (ETH), we achieve the following results in this paper: The scheduling problem on a constant number m of identical machines, which is denoted as Pm‖Cmax, is known to admit a fully polynomial time approximation scheme (FPTAS) of running time O(n) + (1/∊)O(m) (indeed, the algorithm works for an even more general problem where machines are unrelated). We prove this algorithm is essentially the best possible in the sense that a (1/∊)O(m1–5) + nO(1) time FPTAS for any δ > 0 implies that ETH fails. The scheduling problem on an arbitrary number of identical machines, which is denoted as P‖Cmax, is known to admit a polynomial time approximation scheme (PTAS) of running time 2O(1/∊2log3(1/∊)) + nO(1). We prove this algorithm is nearly optimal in the sense that a 2O((1/∊)1–5) + nO(1) time PTAS for any δ > 0 implies that ETH fails, leaving a small room for improvement. In addition, we also consider exact algorithms for the scheduling problem and prove the following result: The traditional dynamic programming algorithm for P‖Cmax is known to run in 2O(n) time. We prove this is essentially the best possible in the sense that even if we restrict that there are n jobs and the processing time of each job is bounded by O(n), an exact algorithm of running time 2(n1–5) for any δ > 0 implies that ETH fails. To obtain these results we will provide two new reductions from 3SAT, one for P‖Cmax and another for P‖Cmax. Indeed, the new reductions explore the structure of scheduling problems and can also lead to other interesting results. For example, using the framework of our reduction for P‖Cmax, Chen et al. [5] are able to prove the APX-hardness of the scheduling problem in which the matrix of job processing times P = (pij)m×n is of rank 3, solving the open problem mentioned in [2].

We study the two-dimensional bin packing problem: Given a list of n rectangles the objective is to find a feasible, i.e. axis-parallel and non-overlapping, packing of all rectangles into the minimum number of unit sized squares, also called bins. Our problem consists of two versions; in the first version it is not allowed to rotate the rectangles while in the other it is allowed to rotate the rectangles by 90°, i.e. to exchange the widths and the heights. Two-dimensional bin packing is a generalization of its one-dimensional counterpart and is therefore strongly -hard. Furthermore Bansal et al. [2] showed that even an is ruled out for this problem, unless . This lower bound of asymptotic approximability was improved by Chlebík & Chlebíková [4] to values 1 + 1/3792 and 1 + 1/2196 for the version with and without rotations, respectively. On the positive side there is an asymptotic 1.69‥ approximation by Caprara [3] without rotations and an asymptotic 1.52… approximation by Bansal et al. [1] for both versions. We give a new asymptotic upper bound for both versions of our problem: For any fixed ε and any instance that fits optimally into OPT bins, our algorithm computes a packing into (1.5 + ε) · OPT+ 69 bins with polynomial running time in the input length. In our new technique we consider an optimal packing of the rectangles into the bins. We cut a small vertical or horizontal strip out of each bin and move the intersecting rectangles into additional bins. This enables us to either round the widths of all wide rectangles, or the heights of all long rectangles in this bin. After this step we round the other, unrounded side of these rectangles and we achieve a solution with a simple structure and only few types of rectangles. Our algorithm initially rounds the instance and computes a solution that nearly matches the modified optimal solution.

In this paper we study a scheduling problem with moldable and non-moldable parallel tasks on $m$ processors. A non-moldable parallel task is one that runs in parallel on a specific given number of processors. The goal is to find a non-preemptive schedule on the m processors which minimizes the makespan, or the latest task completion time. The previous best result is the list scheduling algorithm with an absolute approximation ratio of 2. On the other hand, there does not exist an approximation algorithm for scheduling non-moldable parallel tasks with ratio smaller than 1.5, unless P=NP. In this paper we show that a schedule with length (1.5 + ε) OPT can be computed for the scheduling problem in time O(n log n) + f(1/ε). Furthermore we present an (1.5 + ε) approximation algorithm for scheduling moldable parallel tasks.

We study the following square packing problem: Given a set Q of squares with positive profits, the goal is to pack a subset of Q into a rectangular bin $\mathcal R$ so that the total profit of the squares packed in $\mathcal R$ is maximized. Squares must be packed so that their sides are parallel to those of $\mathcal R$. We present a polynomial time approximation scheme for the problem, which for any value $\epsilon > 0$ finds and packs a subset $Q' \subseteq Q$ of profit at least $(1-\epsilon) OPT$, where $OPT$ is the profit of an optimum solution.

We study two closely related problems in nonpreemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or nonavailability intervals during which the machines are not available; in both cases, the objective is to minimize the makespan. Both formulations have different applications, for example, in turnaround scheduling or overlay computing. For both problems we contribute approximation algorithms with an improved ratio of 3/2. For scheduling with fixed jobs, a lower bound of 3/2 on the approximation ratio has been obtained by Scharbrodt et al. [1999]; for scheduling with nonavailability we provide the same lower bound. We use dual approximation, creation of a gap structure, and a PTAS for the multiple subset sum problem, combined with a postprocessing step to assign large jobs.

For t >0 and g ≥0, a vertex-weighted graph of total weight W is ( t , g ) -trimmable if it contains a vertex-induced subgraph of total weight at least (1−1/ t ) W and with no simple path of more than g edges. A family of graphs is trimmable if for every constant t >0, there is a constant g ≥0 such that every vertex-weighted graph in the family is ( t , g )-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. We also show that every family of directed graphs of bounded layer bandwidth (a less restrictive condition than bounded directed bandwidth) is trimmable. As an application of these results, we derive polynomial-time approximation schemes for various forms of the problem of labeling a subset of given weighted point features with nonoverlapping sliding axes-parallel rectangular labels so as to maximize the total weight of the labeled features, provided that the ratios of label heights or the ratios of label lengths are bounded by a constant. This settles one of the last major open questions in the theory of map labeling.

In this paper we study variants of the nonpreemptive parallel job scheduling problem in which the number of machines is polynomially bounded in the number of jobs. For this problem we show that a schedule with length at most $(1+\varepsilon)\,\mathrm{OPT}$ can be calculated in polynomial time. Unless $P=NP$, this is the best possible result (in the sense of approximation ratio), since the problem is strongly NP-hard. For the case where all jobs must be allotted to a subset of consecutive machines, a schedule with length at most $(1.5+\varepsilon)\,\mathrm{OPT}$ can be calculated in polynomial time. The previously best known results are algorithms with absolute approximation ratio 2. Furthermore, we extend both algorithms to the case of malleable jobs with the same approximation ratios.

We present an efficient polynomial time approximation scheme (EPTAS) for scheduling on uniform processors, i.e., finding a minimum length schedule for a set of n independent jobs on m processors with different speeds (a fundamental NP-hard scheduling problem). The previous best polynomial time approximation scheme (PTAS) by Hochbaum and Shmoys has a running time of $(n/\epsilon)^{O(1/\epsilon^2)}$. Our algorithm, based on a new mixed integer linear program (MILP) formulation with a constant number of integral variables and an interesting rounding method, finds a schedule whose length is within a relative error $\epsilon$ of the optimum and has a running time of $2^{O(1/\epsilon^2\log(1/\epsilon)^3)}+poly(n)$.

We study two closely related problems in non-preemptive scheduling of sequential jobs on identical parallel machines. In these two settings there are either fixed jobs or non-availability intervals during which the machines are not available; in either case, the objective is to minimize the makespan. Both formulations have different applications, e.g. in turnaround scheduling or overlay computing. For both problems we contribute approximation algorithms with an improved ratio of 3/2 + ∊, respectively. For scheduling with fixed jobs, a lower bound of 3/2 on the approximation ratio has been obtained by Scharbrodt, Steger & Weisser; for scheduling with non-availability we provide the same lower bound. In total, our approximation ratio for both problems is essentially tight via suitable inapproximability results. We use dual approximation, creation of a gap structure and job configurations, and a PTAS for the multiple subset sum problem. However, the main feature of our algorithms is a new technique for the assignment of large jobs via flexible rounding. Our new technique is based on an interesting cyclic shifting argument in combination with a network flow model for the assignment of jobs to large gaps.

The multiple knapsack problem (MKP) is a well-known generalization of the classical knapsack problem. We are given a set A of n items and set B of m bins (knapsacks) such that each item a ∊ A has a size size(a) and a profit value profit(a), and each bin b ∊ B has a capacity c(b). The goal is to find a subset U ⊂ A of maximum total profit such that U can be packed into B without exceeding the capacities. The decision version of MKP is strongly NP-complete, since it is a generalization of the classical knapsack and bin packing problem. Furthermore, MKP does not admit an FPTAS even if the number m of bins is two. Kellerer gave a PTAS for MKP with identical capacities and Chekuri and Khanna presented a PTAS for MKP with general capacities with running time . In this paper we propose an EPTAS with parameterized running time . poly(n) + O(m) for MKP. This solves also an open question by Chekuri and Khanna.

The multiple knapsack problem (MKP) is a well-known generalization of the classical knapsack problem. We are given a set A of n items and set B of m bins (knapsacks) such that each item $a \in A$ has a size $size(a)$ and a profit value $profit(a)$, and each bin $b \in B$ has a capacity $c(b)$. The goal is to find a subset $U \subset A$ of maximum total profit such that U can be packed into B without exceeding the capacities. The decision version of MKP is strongly NP-complete, since it is a generalization of the classical knapsack and bin packing problem. Furthermore, MKP does not admit a fully time polynomial time approximation scheme (FPTAS) even if the number m of bins is two. Kellerer gave a polynomial time approximation scheme (PTAS) for MKP with identical capacities and Chekuri and Khanna presented a PTAS for MKP with general capacities with running time $n^{O(\log(1/\epsilon)/\epsilon^8)}$. In this paper we propose an efficient PTAS (EPTAS) with parameterized running time $2^{O(\log(1/\epsilon)/\epsilon^5)} \cdot poly(n) + O(m)$ for MKP. This also solves an open question by Chekuri and Khanna.

We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9 + ϵ and 8 + ϵ, as well as an algorithm with approximation ratio 7 + ϵ that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z -axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 + ϵ and 5 + ϵ, respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29/4, improving the previously best known result of 45/4.

We study resource constrained scheduling problems where the objective is to compute feasible preemptive schedules minimizing the makespan and using no more resources than what are available. We present approximation schemes along with some inapproximability results showing how the approximability of the problem changes in terms of the number of resources. The results are based on linear programming formulations (though with exponentially many variables) and some interesting connections between resource constrained scheduling and (multidimensional, multiple-choice, and cardinality constrained) variants of the classical knapsack problem. In order to prove the results we generalize a method by Grigoriadis et al. for the max-min resource sharing problem to the case with weak approximate block solvers (i.e., with only constant, logarithmic, or even worse approximation ratios). Finally, we present applications of the above results in fractional graph coloring and multiprocessor task scheduling.

In this article, we study the problem of scheduling malleable tasks with precedence constraints. We are given m identical processors and n tasks. For each task the processing time is a function of the number of processors allotted to it. In addition, the tasks must be processed according to the precedence constraints. The goal is to minimize the makespan (maximum completion time) of the resulting schedule. The best previous approximation algorithm (that works in two phases) in Lepère et al. [2002b] has a ratio 3 + √5≈ 5.236. We develop an improved approximation algorithm with a ratio at most 100/43 + 100(√4349 − 7)/2451 ≈ 4.730598. We also show that our resulting ratio is asymptotically tight.

In this paper we propose an approximation algorithm for scheduling malleable tasks with precedence constraints. Based on an interesting model for malleable tasks with continuous processor allotments by Prasanna and Musicus [22, 23, 24], we define two natural assumptions for malleable tasks: the processing time of any malleable task is non-increasing in the number of processors allotted, and the speedup is concave in the number of processors. We show that under these assumptions the work function of any malleable task is non-decreasing in the number of processors and is convex in the processing time.Furthermore, we propose a two-phase approximation algorithm for the scheduling problem. In the first phase we solve a linear program to obtain a fractional allotment for all tasks. By rounding the fractional solution, each malleable task is assigned a number of processors. In the second phase a variant of the list scheduling algorithm is employed. In the phases we use two parameters μ ∈{1... ⌊ (m+1)/2⌋} and ρ ∈ [0,1] for the allotment and the rounding, respectively, where m is the number of processors. By choosing appropriate values of the parameters, we show (via a nonlinear program) that the approximation ratio of our algorithm is at most 100/63+100(√6469+13)/5481 ≈ 3.291919. We also show that our result is very close to the best asymptotic one.

We present an asymptotic fully polynomial time approximation scheme for two-dimensional strip packing with rotations. In this problem, a set of rectangles need to be packed into a rectangle (strip) of fixed width and minimum height, and these rectangles can be rotated by 90°. Additionally, we present a simple asymptotic polynomial time approximation scheme, and give an improved algorithm for two-dimensional bin packing with rotations.

A disk graph is the intersection graph of a set of disks with arbitrary diameters in the plane. For the case that the disk representation is given, we present polynomial-time approximation schemes (PTASs) for the maximum weight independent set problem (selecting disjoint disks of maximum total weight) and for the minimum weight vertex cover problem in disk graphs. These are the first known PTASs for $\mathcal{NP}$-hard optimization problems on disk graphs. They are based on a novel recursive subdivision of the plane that allows applying a shifting strategy on different levels simultaneously, so that a dynamic programming approach becomes feasible. The PTASs for disk graphs represent a common generalization of previous results for planar graphs and unit disk graphs. They can be extended to intersection graphs of other "disk-like" geometric objects (such as squares or regular polygons), also in higher dimensions.

The max-bisection and min-bisection problems are to find a partition of the vertices of a graph into two equal size subsets that, respectively, maximizes or minimizes the number of edges with endpoints in both subsets. We design the first polynomial time approximation scheme for the max-bisection problem on arbitrary planar graphs solving a long-standing open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max- and min-bisection, which could be of independent interest. Using a similar method we design also the first polynomial timeapproximation scheme for max-bisection on unit disk graphs (which could also be easily extended to other geometrically defined graphs).

We study the problem of scheduling n independent tasks on a set of m parallel processors, where the execution time of a task is a function of the subset of processors assigned to the task. For any fixed m, we propose a fully polynomial approximation scheme that for any fixed $\epsilon > 0$ finds a preemptive schedule of length at most $(1+\epsilon)$ times the optimum in $O(n)$ time. We also discuss the nonpreemptive variant of the problem, and present for any fixed m a polynomial approximation scheme that computes an approximate solution of any fixed accuracy in linear time. In terms of the running time, this linear complexity bound gives a substantial improvement of the best previously known polynomial bound [J. Chen and A. Miranda, SIAM J. Comput., 31 (2001), pp. 1--17].

In a graph coloring, each color class induces a disjoint union of isolated vertices. A graph subcoloring generalizes this concept, since here each color class induces a disjoint union of complete graphs. Erdos and, independently, Albertson et al., proved that every graph of maximum degree at most 3 has a 2-subcoloring. We point out that this fact is best possible with respect to degree constraints by showing that the problem of recognizing 2-subcolorable graphs with maximum degree 4 is NP-complete, even when restricted to triangle-free planar graphs. Moreover, in general, for fixed k, recognizing k-subcolorable graphs is NP-complete on graphs with maximum degree at most k 2 . In contrast, we show that, for arbitrary k, k-SUBCOLORABILITY can be decided in linear time on graphs with bounded treewidth and on graphs with bounded cliquewidth (including cographs as a specific case).

In this paper we present a linear time approximation scheme for the job shop scheduling problem with a fixed number of machines and fixed number of operations per job. This improves on the previously best $2+\epsilon$, $\epsilon > 0$, approximation algorithm for the problem by Shmoys, Stein, and Wein [SIAM J. Comput., 23 (1994), pp. 617--632]. Our approximation scheme is very general and it can be extended to the case of job shop scheduling problems with release and delivery times, multistage job shops, dag job shops, and preemptive variants of most of these problems.

A bidirected tree is the directed graph obtained from an undirected tree by replacing each undirected edge by two directed edges with opposite directions. Given a set of directed paths in a bidirected tree, the goal of the maximum edge-disjoint paths problem is to select a maximum-cardinality subset of the paths such that the selected paths are edge-disjoint. This problem can be solved optimally in polynomial time for bidirected trees of constant degree but is APX-hard for bidirected trees of arbitrary degree. For every fixed $\varepsilon >0$, a polynomial-time $(5/3+\varepsilon)$-approximation algorithm is presented.

We consider the problem of scheduling n independent jobs on m unrelated parallel machines.Each job has to be processed by exactly one machine, processing job j on machine i requires p;j time units, and the objective is to minimize the makespan, i.e. the maximum job completion time.We focus on the caSe when n is fixed and develop a fully polynomial approximation scheme whose running time depends only linearly on n.In the second half of the paper we extend this result to a variant of the problem, where processing job j on machine i also incurs a cost of cij, and thus there are two optimization criteria: makespan and cost.We show that for any fixed m, there is a fully polynomial approximation scheme that, given values T and C, computes for any fixed E > 0 a schedule in O(n) time with makespan at most (1 + e)T and cost at most (1 + e)C, if there exists a schedule of makespan T and cost C.

A vertex (edge) coloring $\phi:V\rightarrow \{1,2,\ldots ,t\}$ ($\phi':E\rightarrow \{1,2,\ldots,$ $t\}$) of a graph G=(V,E) is a vertex (edge) t-ranking if, for any two vertices (edges) of the same color, every path between them contains a vertex (edge) of larger color. The {\em vertex ranking number} $\chi_{r}(G)$ ({\em edge ranking number} $\chi_{r}'(G)$) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the {\sc Vertex Ranking} and {\sc Edge Ranking} problems. It is shown that $\chi_{r}(G)$ can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize the graphs where the vertex ranking number $\chi_{r}$ and the chromatic number $\chi$ coincide on all induced subgraphs, show that $\chi_{r}(G)=\chi (G)$ implies $\chi (G)=\omega (G)$ (largest clique size), and give a formula for $\chi_{r}'(K_n)$.

Abstract This paper presents heuristics that are based on a tour splitting of a general routing tour for solving the general capacitated routing problem (GCRP). This problem is a generalization of the vehicle routing problem (VRP) and the capacitated arc routing problem (CARP). For the VRP, heuristics that consist of an optimum partitioning of a TSP tour generated by Christofides are known and have a worst‐case error of 7/2 − 3/ q for even q , where q is the capacity of the vehicles. If we apply a partitioning to an optimum TSP tour, the worst‐case error becomes 3 − 2/ q for even q . We generalize these results to the GCRP and give also some lower bounds. © 1993 John Wiley & Sons, Inc.