Klaus Jansen

collaborators

4 papers

cs.CC2026

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 $f (k, Δ) \cdot ∣ I ∣^{O (1)}$ for integer linear programs with 4-block structure, parameterized by the maximum bl…

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 {Δ, ∥ b ∥_{\infty}})^{O (m^{2})}$ , where $m$ is the number of constraints, $n…

cs.DS2025

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…

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…