Department of Computer Science and Engineering, Michigan State University, East Lansing, MI 48824, USA
Abstract:
We show that the greedy highest density first (HDF) algorithm is (1+ε)-speed O(1)-competitive for the problem of minimizing the ?p norms of weighted flow time on m identical machines. Similar results for minimizing unweighted flow provide insight into the power of migration.