Additive approximation and approximation schemes for load balancing

Many applications in discrete optimization lead to hard problems. Under common assumption, it is impossible to find an algorithm that (1) is efficient, (2) finds an optimal solution on (3) every instance. At least one of these requirements needs to be sacrificed to cope with these problems. In the area of approximation algorithms, the goal is to design algorithms that efficiently find provably good solutions. Typically, for approximation algorithms, provably good implies that we bound the approximation ratio of the value of the solution to the optimal value. One important reason for studying approximation algorithms is that often even on simplified problems, they give us insights in how to design heuristics for the real problem that needs to be solved. Furthermore, having a mathematical proof for an approximation guarantee often results in a deeper understanding of the structure of the underlying problem. Unfortunately, in some cases finding a guarantee on the approximation ratio is impossible, e.g., when the optimal solution value is 0. Or the approximation guarantee is overly pessimistic, e.g., Graham’s (1966) seminal List Scheduling algorithm for makespan scheduling is guaranteed to find a solution with value at most twice the optimal value, but when processing times are small List Scheduling performs much better. To overcome these issues, we consider the concept of additive approximation algorithms. Instead of bounding the ratio, in additive approximation we bound the absolute difference between the value of the solution of the approximation algorithm and the optimal solution value. We apply the concept of additive approximation and additive approximation schemes, that can get arbitrarily close to an optimal solution, for several load balancing problems.