4 papers · 1 filter
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…
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…
Structural Results for High-Multiplicity Scheduling on Uniform Machines
Hauke Brinkop, David Fischer, Klaus Jansen
Parameterizing by the largest processing time and the number of different job processing times , we propose a proximity technique for High-Multiplicity Scheduling on U…
Solving Cut-Problems in Quadratic Time for Graphs With Bounded Treewidth
Hauke Brinkop, Klaus Jansen
In the problem (Unweighted) Max-Cut we are given a graph and asked for a set such that the number of edges from to is maximal. In th…