Hauke Brinkop

collaborators

3 papers

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

Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee

Hauke Brinkop, David Fischer, Klaus Jansen

We consider the problem of scheduling $n$ jobs on $m$ uniform machines while minimizing the makespan ( $Q ∣∣ C_{m a x}$ ) and maximizing the minimum completion time ( $Q ∣∣ C_{m i n}$ ) in a…

cs.DS2024

Structural Results for High-Multiplicity Scheduling on Uniform Machines

Hauke Brinkop, David Fischer, Klaus Jansen

Parameterizing by the largest processing time $p_{ma x}$ and the number of different job processing times $d$ , we propose a proximity technique for High-Multiplicity Scheduling on U…