Description
EGERVÁRY SZEMINÁRIUM
Abstract:
The generalized assignment problem can be viewed as a
scheduling problem with machine load restrictions and costs. Shmoys
and Tardos developed an algorithm that, given a cost value C and
maximum load T, either proves that no feasible schedule exists, or
else finds a schedule of cost at most C, where each machine is used
for at most 2T time units. To prove this, they introduce a new
rounding technique. Later, Azar and Epstein used this new rounding
method to show that there is a 2-approximation algorithm for
minimizing the l_p norm of the load of the machines. I will present
the results of Shmoys and Tardos, together with its application to the
l_p norm minimization problem.