Fair Scheduling via Iterative Quasi-Uniform Sampling

DOI10.1137/18M1202451zbMath1455.90068OpenAlexW3040528764MaRDI QIDQ3304734

Benjamin Moseley, Sungjin Im

Publication date: 3 August 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/18m1202451

zbMATH Keywords

schedulingapproximation algorithmsLP rounding\(\ell_2\)-norm

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Greedy multiprocessor server scheduling
• Approximation Techniques for Average Completion Time Scheduling
• Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling
• Weighted geometric set cover via quasi-uniform sampling
• Minimizing average flow time on related machines
• Minimizing Flow-Time on Unrelated Machines
• Scalably scheduling processes with arbitrary speedup curves
• Longest Wait First for Broadcast Scheduling [Extended Abstract]
• On Column-Restricted and Priority Covering Integer Programs
• On randomized online scheduling
• Approximation schemes for preemptive weighted flow time
• Multi-processor scheduling to minimize flow time with ε resource augmentation
• The Complexity of Scheduling for p-Norms of Flow and Stretch
• Minimizing weighted flow time
• A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation
• The Geometry of Scheduling
• A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time
• Server Scheduling to Balance Priorities, Fairness, and Average Quality of Service
• Scheduling

This page was built for publication: Fair Scheduling via Iterative Quasi-Uniform Sampling