The Complexity of Scheduling for p-norms of Flow and Stretch

Benjamin Moseley, Kirk Pruhs, Cliff Stein

We consider computing optimal k-norm preemptive schedules of jobs that arrive over time. In particular, we show that computing the optimal k-norm of flow schedule, is strongly NP-h…