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 , where is the number of constraints, $n…
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 jobs on uniform machines while minimizing the makespan () and maximizing the minimum completion time () in a…
cs.DS2023
New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
Sebastian Berndt, Hauke Brinkop, Klaus Jansen +2
Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs d…