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

2013/01/04 by Benjamin Moseley, Kirk Pruhs, Moseley, Benjamin +3
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms

paper · pdf · doi:10.48550/arxiv.1301.0793

openalex publication_date 2013/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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-hard for k in (0, 1) and integers k in (1, infinity). Further we show that computing the optimal k-norm of stretch schedule, is strongly NP-hard for k in (0, 1) and integers k in (1, infinity).

Related

• A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines
• Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs
• Total stretch minimization on single and identical parallel machines
• The Complexity of Mean Flow Time Scheduling Problems with Release Times
• Approximate Deadline-Scheduling with Precedence Constraints