@book{b5ced370bcb445e4a97bb81ec5b811f0,
title = "Quality of Move-Optimal Schedules for Minimizing the Vector Norm of the Workloads",
abstract = "We study the problem of minimizing the vector norm $||\cdot||_p$ of the workloads. We examine move-optimal assignments and prove a performance guarantee of $\frac{2^p-1}{p} \cdot \left(\frac{p-1}{2^p-2}\right)^{\frac{p-1}{p}},$ for any integer $p>1$ and moreover, we show that this guarantee is tight. Additionally, we consider assignments obtained by applying the LPT-heuristic of Graham (1969). We prove that an LPT-assignment has a performance guarantee of $\frac{3^p-2^p}{p} \cdot \left(\frac{p-1}{2 \cdot 3^p - 3 \cdot 2^p}\right)^{\frac{p-1}{p}},$ which reproves a result of Chandra and Wong (1975).",
keywords = "EWI-7596, METIS-238242, IR-66527, MSC-90B35",
author = "T. Brueggemann and Hurink, {Johann L.}",
note = "eemcs-eprint-7596 ",
year = "2006",
language = "Undefined",
series = "Applied Mathematics Memoranda",
publisher = "Universiteit Twente, Faculteit Toegepaste Wiskunde",
number = "1808",
}