Explorable uncertainty in scheduling with non-uniform testing times

DOI10.1007/978-3-030-80879-2_9MaRDI QIDQ2117694zbMATH OpenOpenAlexFDO

Authors Susanne Albers, Alexander Eckl

Publication date 22 March 2022

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2009.13316

zbMATH Keywords

competitive analysisexplorable uncertaintymakespanonline schedulingsingle machinesum of completion times

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites work

• Computing minimum spanning trees with uncertainty
• Computing shortest paths with uncertainty
• Computing the Median with Uncertainty
• Efficient update strategies for geometric computing with uncertainty
• scientific article; zbMATH DE number 7075885 (Why is no real title available?)
• Optimal Search for the Best Alternative
• Query strategies for priced information
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Scheduling with explorable uncertainty
• Scheduling. Theory, algorithms, and systems
• The price of information in combinatorial optimization
• The robust knapsack problem with queries
• The update complexity of selection and related problems

Cited in

(14)

• Scheduling with a processing time oracle
• Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing
• Round-competitive algorithms for uncertainty problems with parallel queries
• Improved approximation algorithms for multiprocessor scheduling with testing
• Stochastic graph exploration with limited resources
• Approximation Algorithms for Multiprocessor Scheduling with Testing to Minimize the Total Job Completion Time
• The power of amortization on scheduling with explorable uncertainty
• Scheduling with testing: competitive algorithms for minimizing the total weighted completion time in the adversarial model
• Perpetual scheduling with explorable uncertainty
• Learning-augmented query policies for minimum spanning tree with uncertainty
• Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling
• Scheduling with obligatory tests
• Randomized algorithms for fully online multiprocessor scheduling with testing
• Scheduling with testing on multiple identical parallel machines

This page was built for publication: Explorable uncertainty in scheduling with non-uniform testing times

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