A lower bound for randomized on-line scheduling algorithms

DOI10.1016/0020-0190(94)00110-3MaRDI QIDQ1336752zbMATH OpenOpenAlexFDO

Authors Bo Chen, Gerhard J. Woeginger, André van Vliet

Publication date 19 September 1995

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)00110-3

zbMATH Keywords

combinatorial problemson-line algorithmsrandomizationschedulingworst case bounds

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Combinatorics in computer science (68R05) Distributed algorithms (68W15)

Recommendations

• A lower bound for randomized on-line multiprocessor scheduling
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• scientific article; zbMATH DE number 1894930
• Randomized algorithms for that ancient scheduling problem
• A lower bound for on-line scheduling on uniformly related machines

Cites work

• Bounds for Certain Multiprocessing Anomalies

Cited in

(32)

• Preemptive online scheduling: Optimal algorithms for all speeds
• A better lower bound for on-line scheduling
• Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling
• Randomized on-line scheduling on three processors.
• Resource augmentation in load balancing.
• New algorithms for related machines with temporary jobs.
• On-line scheduling revisited
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• Improved lower bounds for online scheduling to minimize total stretch
• Scheduling with limited machine availability
• A lower bound for on-line scheduling on uniformly related machines
• Scheduling In the random-order model
• Barely random algorithms for multiprocessor scheduling
• Randomized on-line scheduling similar jobs to minimize makespan on two identical processors
• An on-line LS algorithm for some \(Q_m|r_j|C_{\max}\) scheduling
• A lower bound for randomized on-line multiprocessor scheduling
• Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
• A guessing game and randomized online algorithms
• Semi-online scheduling revisited
• Online algorithms with advice for bin packing and scheduling problems
• Online makespan minimization: the power of restart
• On-line load balancing for related machines
• Randomized algorithms for that ancient scheduling problem
• Semi-online scheduling with decreasing job sizes
• Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
• Preemptive multiprocessor scheduling with rejection
• On-line bin-stretching
• An optimal online algorithm for scheduling two machines with release times
• Scheduling in the random-order model
• Scheduling with testing on multiple identical parallel machines
• Preemptive scheduling on a small number of hierarchical machines
• Randomized priority algorithms

This page was built for publication: A lower bound for randomized on-line scheduling algorithms

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