6 papers
Compressing the Lawler-Moore Dynamic Program for Weighted Tardy Jobs
Klaus Jansen, Björn Schumacher, Corinna Wambsganz
The classic scheduling problem of minimizing the total weight of tardy jobs () asks for a schedule of jobs each with a processing time, weight, and due date on a…
An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints
Klaus Jansen, Dirk Nowotka, Lis Pirotton +2
Patterns are words with terminals and variables. The language of a pattern is the set of words obtained by uniformly substituting all variables with words that contain only termina…
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 maximu…
Equivalent Instances for Scheduling and Packing Problems
Klaus Jansen, Kai Kahler, Corinna Wambsganz
Two instances and of a parameterized problem are equivalent if they have the same set of solutions (static equivalent) or if the set of solutions of c…
An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints
Klaus Jansen, Dirk Nowotka, Lis Pirotton +2
Patterns are words with terminals and variables. The language of a pattern is the set of words obtained by uniformly substituting all variables with words that contain only termina…
Minimizing the Weighted Makespan with Restarts on a Single Machine
Aflatoun Amouzandeh, Klaus Jansen, Lis Pirotton +2
We consider the problem of minimizing the weighted makespan on a single machine with restarts. Restarts are similar to preemptions but weaker: a job can be interrupted, but then it…