A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio.
Elisabeth LübbeckeOlaf MaurerNicole MegowAndreas WiesePublished in: ACM Trans. Algorithms (2016)
Keyphrases
- competitive ratio
- online algorithms
- identical parallel machines
- single machine
- lower bound
- optimal strategy
- online learning
- average case
- scheduling problem
- initially unknown
- worst case
- processing times
- convergence rate
- asymptotically optimal
- release dates
- upper bound
- learning algorithm
- decision problems
- resource allocation
- optimal solution
- parallel machines