A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
From MaRDI portal
Publication:3792237
DOI10.1137/0217033zbMath0647.68040WikidataQ101128280 ScholiaQ101128280MaRDI QIDQ3792237
Dorit S. Hochbaum, David B. Shmoys
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/b24d9c2bfec98a09b0c38cfe6a2b91f4f4a69657
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
Related Items
On the Complexity of Scheduling to Optimize Average Response Time, Dynamic scheduling in manufacturing systems using Brownian approximations, On-line bin-stretching, Approximation algorithms for scheduling with reservations, Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays, Approximation algorithms for scheduling unrelated parallel machines, Linear time algorithms for parallel machine scheduling, Deterministic monotone algorithms for scheduling on related machines, Nash equilibria in discrete routing games with convex latency functions, Preemptive online scheduling: Optimal algorithms for all speeds, Fair cost-sharing methods for scheduling jobs on parallel machines, Tighter approximation bounds for LPT scheduling in two special cases, A linear compound algorithm for uniform machine scheduling, A note on MULTIFIT scheduling for uniform machines, Minimizing average completion time in the presence of release dates, Feasibility of scheduling lot sizes of two frequencies on one machine, On the existence of schedules that are near-optimal for both makespan and total weighted completion time, Parallel machine batching and scheduling with deadlines, On-line scheduling with precedence constraints, Polynomial time approximation algorithms for machine scheduling: Ten open problems, Approximability of scheduling with fixed jobs, New approximation bounds for LPT scheduling, An optimal rounding gives a better approximation for scheduling unrelated machines, Vector assignment schemes for asymmetric settings, Selfish unsplittable flows, Optimal preemptive scheduling for general target functions, Approximations and auctions for scheduling batches on related machines, SCHEDULING TO MINIMIZE MAX FLOW TIME: OFF-LINE AND ON-LINE ALGORITHMS, Optimal File-Distribution in Heterogeneous and Asymmetric Storage Networks, A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
