A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
From MaRDI portal
Publication:3792237
DOI10.1137/0217033zbMath0647.68040OpenAlexW2014071862WikidataQ101128280 ScholiaQ101128280MaRDI QIDQ3792237
David B. Shmoys, Dorit S. Hochbaum
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/b24d9c2bfec98a09b0c38cfe6a2b91f4f4a69657
Related Items
Vertex cover meets scheduling ⋮ Feasibility of scheduling lot sizes of two frequencies on one machine ⋮ New Algorithmic Results for Bin Packing and Scheduling ⋮ Towards Tight Lower Bounds for Scheduling Problems ⋮ Task scheduling in networks ⋮ On the Complexity of Scheduling to Optimize Average Response Time ⋮ New approximation bounds for LPT scheduling ⋮ Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ Linear time algorithms for parallel machine scheduling ⋮ Approximations and auctions for scheduling batches on related machines ⋮ An AFPTAS for variable sized bin packing with general activation costs ⋮ ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER ⋮ Complete formulations of polytopes related to extensions of assignment matrices ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ On the existence of schedules that are near-optimal for both makespan and total weighted completion time ⋮ Approximation guarantee of OSP mechanisms: the case of machine scheduling and facility location ⋮ ONLINE SCHEDULING OF MIXED CPU-GPU JOBS ⋮ A truthful constant approximation for maximizing the minimum load on related machines ⋮ Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays ⋮ A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring ⋮ Moderately exponential approximation for makespan minimization on related machines ⋮ A unified framework for designing EPTAS for load balancing on parallel machines ⋮ Smoothed performance guarantees for local search ⋮ Worst-case analysis of LPT scheduling on a small number of non-identical processors ⋮ Same‐day deliveries in omnichannel retail: Integrated order picking and vehicle routing with vehicle‐site dependencies ⋮ Online load balancing on uniform machines with limited migration ⋮ EPTAS for parallel identical machine scheduling with time restrictions ⋮ The price of envy-freeness in machine scheduling ⋮ On the complexity of scheduling unrelated parallel machines with limited preemptions ⋮ Optimizing performance and reliability on heterogeneous parallel systems: approximation algorithms and heuristics ⋮ Graph balancing: a special case of scheduling unrelated parallel machines ⋮ An efficient polynomial time approximation scheme for load balancing on uniformly related machines ⋮ Approximability of scheduling with fixed jobs ⋮ Improved approximation algorithms for scheduling parallel jobs on identical clusters ⋮ Performance guarantees for scheduling algorithms under perturbed machine speeds ⋮ Online Makespan Scheduling with Job Migration on Uniform Machines ⋮ A Family of Scheduling Algorithms for Hybrid Parallel Platforms ⋮ Symmetry exploitation for online machine covering with bounded migration ⋮ Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds ⋮ Deterministic monotone algorithms for scheduling on related machines ⋮ Scheduling on uniform processors with at most one downtime on each machine ⋮ Approximation algorithms for scheduling on multi-core processor with shared speedup resources ⋮ Nash equilibria in discrete routing games with convex latency functions ⋮ SCHEDULING TO MINIMIZE MAX FLOW TIME: OFF-LINE AND ON-LINE ALGORITHMS ⋮ Partitioned EDF scheduling on a few types of unrelated multiprocessors ⋮ Truthful mechanism design via correlated tree rounding ⋮ Online Scheduling on a CPU-GPU Cluster ⋮ An optimal rounding gives a better approximation for scheduling unrelated machines ⋮ Unnamed Item ⋮ Vector assignment schemes for asymmetric settings ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ An improved lower bound for rank four scheduling ⋮ Dynamic scheduling in manufacturing systems using Brownian approximations ⋮ On-line bin-stretching ⋮ Approximating vector scheduling: almost matching upper and lower bounds ⋮ Approximation algorithms for scheduling with reservations ⋮ A unified view of parallel machine scheduling with interdependent processing rates ⋮ A Unified Approach to Truthful Scheduling on Related Machines ⋮ A PTAS for Scheduling Unrelated Machines of Few Different Types ⋮ Related machine scheduling with machine speeds satisfying linear constraints ⋮ Optimal File-Distribution in Heterogeneous and Asymmetric Storage Networks ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ An EPTAS for scheduling on unrelated machines of few different types ⋮ Preemptive online scheduling: Optimal algorithms for all speeds ⋮ A linear compound algorithm for uniform machine scheduling ⋮ Approximation algorithms for scheduling unrelated parallel machines ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ Makespan minimization with OR-precedence constraints ⋮ Dividing splittable goods evenly and with limited fragmentation ⋮ A note on MULTIFIT scheduling for uniform machines ⋮ Fair cost-sharing methods for scheduling jobs on parallel machines ⋮ Tighter approximation bounds for LPT scheduling in two special cases ⋮ Online makespan scheduling with job migration on uniform machines ⋮ Parallel machine batching and scheduling with deadlines ⋮ A Full Description of Polytopes Related to the Index of the Lowest Nonzero Row of an Assignment Matrix ⋮ Stochastic Load Balancing on Unrelated Machines ⋮ Minimizing average completion time in the presence of release dates ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ Selfish unsplittable flows ⋮ Optimal preemptive scheduling for general target functions ⋮ Fair by design: multidimensional envy-free mechanisms ⋮ Hardness of approximation for knapsack problems ⋮ Balanced partitions of trees and applications ⋮ On-line scheduling with precedence constraints ⋮ Dividing splittable goods evenly and with limited fragmentation ⋮ Performance guarantees of local search for minsum scheduling problems
