Online makespan minimization with budgeted uncertainty

DOI10.1007/978-3-030-83508-8_4OpenAlexW3191776655MaRDI QIDQ832833

Susanne Albers, Maximilian Janke

Publication date: 25 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-83508-8_4

zbMATH Keywords

uncertaintyschedulingcompetitive analysislower boundonline algorithmmakespan minimizationbudgeted uncertainty

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Related Items

A single representative min-max-min robust selection problem with alternatives and budgeted uncertainty

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating a two-machine flow shop scheduling under discrete scenario uncertainty
• Semi-on-line multiprocessor scheduling with given total processing time
• Approximation algorithms for scheduling unrelated parallel machines
• Query-competitive algorithms for cheapest set problems under uncertainty
• Algorithms and complexity analysis for robust single-machine scheduling problems
• Complexity of single machine scheduling problems under scenario-based uncertainty
• New algorithms for an ancient scheduling problem.
• A better lower bound for on-line scheduling
• Robust discrete optimization and network flows
• On-line scheduling revisited
• Scheduling In the random-order model
• An adversarial model for scheduling with testing
• Approximating robust bin packing with budgeted uncertainty
• Robust scheduling with budgeted uncertainty
• Linear Programming under Uncertainty
• The update complexity of selection and related problems
• Parallel Machine Scheduling under Uncertainty
• Online Scheduling with Bounded Migration
• The Power of Reordering for Online Minimum Makespan Scheduling
• Computing the median with uncertainty
• Approximating Single Machine Scheduling with Scenarios
• The Price of Robustness
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Better Bounds for Online Scheduling
• Tight Bounds for Online Vector Scheduling
• A Better Algorithm for an Ancient Scheduling Problem
• Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming
• Bounds for Certain Multiprocessing Anomalies
• Approximation results for makespan minimization with budgeted uncertainty