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 ...
share
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...
research
∙
10/05/2022
The Power of Duality: Response Time Analysis meets Integer Programming
We study a mutually enriching connection between response time analysis ...
research
∙
10/04/2022
Scheduling with Many Shared Resources
Consider the many shared resource scheduling problem where jobs have to ...
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...
research
∙
02/24/2022
A PTAS for Packing Hypercubes into a Knapsack
We study the d-dimensional hypercube knapsack problem where we are given...
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...
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...
research
∙
07/04/2021
Closing the gap for single resource constraint scheduling
In the problem called single resource constraint scheduling, we are give...
research
∙
05/15/2021
Peak Demand Minimization via Sliced Strip Packing
We study Nonpreemptive Peak Demand Minimization (NPDM) problem, where we...
research
∙
04/20/2021
Robust Online Algorithms for Dynamic Choosing Problems
Semi-online algorithms that are allowed to perform a bounded amount of r...
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,...
research
∙
11/12/2020
Total Completion Time Minimization for Scheduling with Incompatibility Cliques
This paper considers parallel machine scheduling with incompatibilities ...
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...
research
∙
08/29/2020
The Double Exponential Runtime is Tight for 2-Stage Stochastic ILPs
We consider fundamental algorithmic number theoretic problems and their ...
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...
research
∙
02/18/2020
Fuzzy Simultaneous Congruences
We introduce a very natural generalization of the well-known problem of ...
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...
research
∙
09/26/2019
Approximation Algorithms for Scheduling with Class Constraints
Assigning jobs onto identical machines with the objective to minimize th...
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...
research
∙
05/21/2019
Approximation results for makespan minimization with budgeted uncertainty
We study approximation algorithms for the problem of minimizing the make...
research
∙
05/20/2019
Robust Online Algorithms for Dynamic Problems
Online algorithms that allow a small amount of migration or recourse hav...
research
∙
04/13/2019
Online Bin Covering with Limited Migration
Semi-online models where decisions may be revoked in a limited way have ...
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 ...
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...
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...
research
∙
10/17/2018
An EPTAS for machine scheduling with bag-constraints
Machine scheduling is a fundamental optimization problem in computer sci...
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...
research
∙
09/27/2018
Scheduling on (Un-)Related Machines with Setup Times
We consider a natural generalization of scheduling n jobs on m parallel ...
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...
research
∙
03/13/2018
On Integer Programming and Convolution
Integer programs with a fixed number of constraints can be solved in pse...
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...
research
∙
12/13/2017
Closing the gap for pseudo-polynomial strip packing
We study pseudo-polynomial Strip Packing. Given a set of rectangular axi...
research
∙
10/31/2017