A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines Without Preemption.

Tomás Ebenlendr Jirí Sgall

Published in: Theory Comput. Syst. (2015)

Keyphrases

online algorithms
lower bound
parallel machines
online learning
competitive ratio
upper bound
scheduling problem
branch and bound algorithm
worst case
learning algorithm
average case
np hard
single machine
optimal solution
decision boundary
data sets
nearest neighbor
special case
processing times
batch processing