A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio

Elisabeth Günther Olaf Maurer Nicole Megow Andreas Wiese

Published in: CoRR (2012)

Keyphrases

competitive ratio
online algorithms
identical parallel machines
single machine
online learning
lower bound

scheduling problem
optimal strategy
average case
processing times
worst case
learning algorithm

asymptotically optimal
initially unknown
completion times
release dates
scheduling algorithm
convergence rate

upper bound
precedence constraints
resource allocation
np hard
special case
optimal solution