Explanipedia

A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times Open

Max A. Deppert, David Fischer, Klaus Jansen · 2025

We consider the $\mathcal{NP}$-hard problem $\mathrm{P} \mathbf{\vert} \mathrm{pmtn, setup=s_i} \mathbf{\vert} \mathrm{C_{\max}}$, the problem of scheduling $n$ jobs, which are divided into $c$ classes, on $m$ identical parallel machines w…

Peak Demand Minimization via Sliced Strip Packing Open

Max A. Deppert, Klaus Jansen, Arindam Khan, Malin Rau, Malte Tutas · 2023

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 p…

A $(3/2 + \varepsilon)$-Approximation for Multiple TSP with a Variable Number of Depots Open

Max A. Deppert, Matthias Kaul, Matthias Mnich · 2023

One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the {\sc Multiple TSP}: a set of $m\geq 1$ salespersons collectively traverses a set of $n$ cities by $m$ non-trivial tours, to minimize the total leng…

The Power of Duality: Response Time Analysis meets Integer Programming Open

Max A. Deppert, Klaus Jansen · 2022

We study a mutually enriching connection between response time analysis in real-time systems and the mixing set problem. Thereby generalizing over known results we present a new approach to the computation of response times in fixed-priori…

Scheduling with Many Shared Resources Open

Max A. Deppert, Klaus Jansen, Marten Maack, Simon Pukrop, Malin Rau · 2022

Consider the many shared resource 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 exe…

Load Balancing: The Long Road from Theory to Practice Open

Sebastian Berndt, Max A. Deppert, Klaus Jansen, Lars Rohwedder · 2022

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 exponent…

Peak Demand Minimization via Sliced Strip Packing Open

Max A. Deppert, Klaus Jansen, Arindam Khan, Malin Rau, Malte Tutas · 2021

We study 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 l…

Peak Demand Minimization via Sliced Strip Packing Open

Max A. Deppert, Klaus Jansen, Arindam Khan, Malin Rau, Malte Tutas · 2021

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 pe…

Fuzzy Simultaneous Congruences Open

Max A. Deppert, Klaus Jansen, Kim-Manuel Klein · 2021

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₁,… ,a_n we consider remainder…

Near-Linear Approximation Algorithms for Scheduling Problems with Batch Setup Times Open

Max A. Deppert, Klaus Jansen · 2019

We investigate the scheduling of $n$ jobs divided into $c$ classes on $m$\nidentical parallel machines. For every class there is a setup time which is\nrequired whenever a machine switches from the processing of one class to\nanother class…

Max A. Deppert YOU? Author Swipe