Scheduling with explorable uncertainty

DOI10.4230/LIPICS.ITCS.2018.30MaRDI QIDQ4993294zbMATH OpenFDO

Authors Thomas Erlebach, Nicole Megow, Julie Meißner, Christoph Dürr

Publication date 15 June 2021

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2018.30

zbMATH Keywords

competitive ratioexplorable uncertaintymakespanonline schedulingsum of completion times

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Recommendations

• An adversarial model for scheduling with testing
• Computing and scheduling with explorable uncertainty
• Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing
• Models and Algorithms for Stochastic Online Scheduling
• Stochastic Scheduling on Unrelated Machines

Cites work

• Computing minimum spanning trees with uncertainty
• Computing shortest paths with uncertainty
• Computing the Median with Uncertainty
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• Randomization helps computing a minimum spanning tree under uncertainty
• The robust knapsack problem with queries
• The update complexity of selection and related problems

Cited in

(19)

• Computing and scheduling with explorable uncertainty
• Scheduling with a processing time oracle
• Explorable uncertainty in scheduling with non-uniform testing times
• Two-stage robust optimization problems with two-stage uncertainty
• Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing
• An adversarial model for scheduling with testing
• A robust optimization approach with probe-able uncertainty
• scientific article; zbMATH DE number 1670525 (Why is no real title available?)
• Query-Competitive Sorting with Uncertainty.
• Euro-Par 2004 Parallel Processing
• Improved approximation algorithms for multiprocessor scheduling with testing
• Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty
• Approximation Algorithms for Multiprocessor Scheduling with Testing to Minimize the Total Job Completion Time
• The power of amortization on scheduling with explorable uncertainty
• Perpetual scheduling with explorable uncertainty
• Randomized algorithms for fully online multiprocessor scheduling with testing
• Scheduling with testing on multiple identical parallel machines
• Online makespan minimization with budgeted uncertainty
• Scheduling search procedures: The wheel of fortune

This page was built for publication: Scheduling with explorable uncertainty

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993294)