Seminar: Moritz Buchem (Maastricht) + Michelle Sweering (CWI)

We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines.
Additive approximation schemes compute a solution with an absolute error in the objective of at most  εh for some suitable parameter h and any given ε > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For these settings we present additive approximation schemes for h = pmax, the maximum processing time of the jobs.

Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots
to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slot-MILP. While it has a linear number of integral variables, we identify structural properties of (near-)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a local-search  algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most εpmax.

This is joint work together with Lars Rohwedder (EPFL), Tjark Vredeveld (UM) and Andreas Wiese (UChile).