Performance guarantees for scheduling algorithms under perturbed machine speeds

DOI10.1016/j.dam.2014.05.041zbMath1325.90039OpenAlexW2011136598MaRDI QIDQ496438

Michael Etscheid

Publication date: 21 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.05.041

zbMATH Keywords

schedulingperformance guaranteeslocal searchsmoothed analysis

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (2)

Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic ⋮ Smoothed Analysis of Local Search Algorithms

Cites Work

• Approximation algorithms for scheduling unrelated parallel machines
• Worst-case Nash equilibria in restricted routing
• Performance Guarantees of Local Search for Multiprocessor Scheduling
• Tight bounds for worst-case equilibria
• Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling
• Smoothed analysis of algorithms
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Bounds for List Schedules on Uniform Processors
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Probability Inequalities for Sums of Bounded Random Variables
• Algorithms and Data Structures
• Random knapsack in expected polynomial time

This page was built for publication: Performance guarantees for scheduling algorithms under perturbed machine speeds