4 papers · 1 filter
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…
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…
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…