Klaus Jansen

collaborators

3 papers

cs.DS2026

The Support of Bin Packing is Exponential

Klaus Jansen, Felix Ohnesorge, Lis Pirotton +1

Consider the classical Bin Packing problem with $d$ different item sizes $s_{i}$ and amounts of items $a_{i} .$ The support of a Bin Packing solution is the number of differently filled…

math.OC2025

Approximation algorithms for integer programming with resource augmentation

Hauke Brinkop, Hua Chen, Lin Chen +2

The classic algorithm [Papadimitriou, J.ACM '81] for IPs has a running time $n^{O (m)} (m \cdot max {I^, ∥ b ∥_{\infty}})^{O (m^{2})}$ , where $m$ is the number of constraints, $…

cs.DS2025

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…