7 papers
A Constructive FPT Algorithm for Integer Cone Optimization with Convex Costs
Klaus Jansen, Felix Ohnesorge
We give a deterministic fixed-parameter algorithm for integer cone optimization with convex costs. Given rational polytopes in , each with a convex cost function,…
A Fixed-Parameter Algorithm for 4-Block Integer Programming
Klaus Jansen, Felix Ohnesorge, Corinna Wambsganz
We give a fixed parameter tractable (FPT) algorithm with running time for integer linear programs with 4-block structure, parameterized by the maximum bl…
Improved Approximation Algorithms for Parallel Task Scheduling and Multiple Cluster Scheduling
Bennet Edler, Klaus Jansen, Felix Ohnesorge +1
In the problem of Parallel Task Scheduling (PTS), we are asked to schedule jobs, each with a fixed processing time and machine requirement, such that the completion time of the…
A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling
Klaus Jansen, Felix Ohnesorge
In moldable job scheduling, we are provided identical machines and jobs that can be executed on a variable number of machines. The execution time of each job depends on the…
The Support of Bin Packing is Exponential
Klaus Jansen, Felix Ohnesorge, Lis Pirotton +1
Consider the classical Bin Packing problem with different item sizes and amounts of items The support of a Bin Packing solution is the number of differently filled…
A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
Klaus Jansen, Felix Ohnesorge, Lis Pirotton
Consider a high-multiplicity Bin Packing instance with distinct item types. In 2014, Goemans and Rothvoss gave an algorithm with runtime for this problem…
Improved Algorithms for Monotone Moldable Job Scheduling using Compression and Convolution
Kilian Grage, Klaus Jansen, Felix Ohnesorge
In the moldable job scheduling problem one has to assign a set of jobs to machines, in order to minimize the time it takes to process all jobs. Each job is moldable, so it…