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).

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.

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.