b'Klaus Jansen'

research

∙ 05/15/2023

New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines

Mixed-integer linear programming (MILP) is at the core of many advanced ...

0 Sebastian Berndt, et al. ∙

research

∙ 03/02/2023

Improved Algorithms for Monotone Moldable Job Scheduling using Compression and Convolution

In the moldable job scheduling problem one has to assign a set of n jobs...

0 Kilian Grage, et al. ∙

research

∙ 10/05/2022

The Power of Duality: Response Time Analysis meets Integer Programming

We study a mutually enriching connection between response time analysis ...

0 Max A. Deppert, et al. ∙

research

∙ 10/04/2022

Scheduling with Many Shared Resources

Consider the many shared resource scheduling problem where jobs have to ...

0 Max A. Deppert, et al. ∙

research

∙ 03/03/2022

High Multiplicity Scheduling on Uniform Machines in FPT-Time

In high-multiplicity scheduling, jobs of the same size are encoded in an...

0 Hauke Brinkop, et al. ∙

research

∙ 02/24/2022

A PTAS for Packing Hypercubes into a Knapsack

We study the d-dimensional hypercube knapsack problem where we are given...

0 Klaus Jansen, et al. ∙

research

∙ 02/16/2022

On the Complexity of Scheduling Problems With a Fixed Number of Parallel Identical Machines

In parallel machine scheduling, we are given a set of jobs, together wit...

0 Klaus Jansen, et al. ∙

research

∙ 07/28/2021

Load Balancing: The Long Road from Theory to Practice

There is a long history of approximation schemes for the problem of sche...

0 Sebastian Berndt, et al. ∙

research

∙ 07/04/2021

Closing the gap for single resource constraint scheduling

In the problem called single resource constraint scheduling, we are give...

0 Klaus Jansen, et al. ∙

research

∙ 05/15/2021

Peak Demand Minimization via Sliced Strip Packing

We study Nonpreemptive Peak Demand Minimization (NPDM) problem, where we...

0 Max A. Deppert, et al. ∙

research

∙ 04/20/2021

Robust Online Algorithms for Dynamic Choosing Problems

Semi-online algorithms that are allowed to perform a bounded amount of r...

0 Sebastian Berndt, et al. ∙

research

∙ 01/03/2021

An optimal FPT algorithm parametrized by treewidth for Weighted-Max-Bisection given a tree decomposition as advice assuming SETH and the hardness of MinConv

The weighted maximal bisection problem is, given an edge weighted graph,...

0 Hauke Brinkop, et al. ∙

research

∙ 11/12/2020

Total Completion Time Minimization for Scheduling with Incompatibility Cliques

This paper considers parallel machine scheduling with incompatibilities ...

0 Klaus Jansen, et al. ∙

research

∙ 10/19/2020

Tightness of Sensitivity and Proximity Bounds for Integer Linear Programs

We consider ILPs, where each variable corresponds to an integral point w...

0 Sebastian Berndt, et al. ∙

research

∙ 08/29/2020

The Double Exponential Runtime is Tight for 2-Stage Stochastic ILPs

We consider fundamental algorithmic number theoretic problems and their ...

0 Klaus Jansen, et al. ∙

research

∙ 06/18/2020

New Bounds for the Vertices of the Integer Hull

The vertices of the integer hull are the integral equivalent to the well...

0 Sebastian Berndt, et al. ∙

research

∙ 02/18/2020

Fuzzy Simultaneous Congruences

We introduce a very natural generalization of the well-known problem of ...

0 Max A. Deppert, et al. ∙

research

∙ 11/30/2019

Exact Polynomial Time Algorithm for the Response Time Analysis of Harmonic Tasks with Constrained Release Jitter

In some important application areas of hard real-time systems, preemptiv...

0 Thi Huyen Chau Nguyen, et al. ∙

research

∙ 09/26/2019

Approximation Algorithms for Scheduling with Class Constraints

Assigning jobs onto identical machines with the objective to minimize th...

0 Klaus Jansen, et al. ∙

research

∙ 07/08/2019

Inapproximability Results for Scheduling with Interval and Resource Restrictions

In the restricted assignment problem, the input consists of a set of mac...

0 Marten Maack, et al. ∙

research

∙ 05/21/2019

Approximation results for makespan minimization with budgeted uncertainty

We study approximation algorithms for the problem of minimizing the make...

0 Marin Bougeret, et al. ∙

research

∙ 05/20/2019

Robust Online Algorithms for Dynamic Problems

Online algorithms that allow a small amount of migration or recourse hav...

0 Sebastian Berndt, et al. ∙

research

∙ 04/13/2019

Online Bin Covering with Limited Migration

Semi-online models where decisions may be revoked in a limited way have ...

0 Sebastian Berndt, et al. ∙

research

∙ 02/09/2019

Linear Time Algorithms for Multiple Cluster Scheduling and Multiple Strip Packing

We study the Multiple Cluster Scheduling problem and the Multiple Strip ...

0 Klaus Jansen, et al. ∙

research

∙ 11/02/2018

Local search breaks 1.75 for Graph Balancing

Graph Balancing is the problem of orienting the edges of a weighted mult...

0 Klaus Jansen, et al. ∙

research

∙ 11/02/2018

Near-Linear Time Algorithm for n-fold ILPs via Color Coding

We study an important case of ILPs {c^Tx Ax = b, l ≤ x ≤ u, x ∈Z^n t...

0 Klaus Jansen, et al. ∙

research

∙ 10/17/2018

An EPTAS for machine scheduling with bag-constraints

Machine scheduling is a fundamental optimization problem in computer sci...

0 Kilian Grage, et al. ∙

research

∙ 10/02/2018

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

We investigate the scheduling of n jobs divided into c classes/batches o...

0 Max A. Deppert, et al. ∙

research

∙ 09/27/2018

Scheduling on (Un-)Related Machines with Setup Times

We consider a natural generalization of scheduling n jobs on m parallel ...

0 Klaus Jansen, et al. ∙

research

∙ 07/10/2018

A note on the integrality gap of the configuration LP for restricted Santa Claus

In the restricted Santa Claus problem we are given resources R and play...

0 Klaus Jansen, et al. ∙

research

∙ 03/13/2018

On Integer Programming and Convolution

Integer programs with a fixed number of constraints can be solved in pse...

0 Klaus Jansen, et al. ∙

research

∙ 01/19/2018

Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times

Integer linear programs of configurations, or configuration IPs, are a c...

0 Klaus Jansen, et al. ∙

research

∙ 12/13/2017

Closing the gap for pseudo-polynomial strip packing

We study pseudo-polynomial Strip Packing. Given a set of rectangular axi...

0 Klaus Jansen, et al. ∙

research

∙ 10/31/2017

Scheduling Monotone Moldable Jobs in Linear Time

A moldable job is a job that can be executed on an arbitrary number of p...

0 Klaus Jansen, et al. ∙

Klaus Jansen

Featured Co-authors