A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio.
Elisabeth GüntherOlaf MaurerNicole MegowAndreas WiesePublished in: SODA (2013)
Keyphrases
- competitive ratio
- online algorithms
- identical parallel machines
- single machine
- lower bound
- scheduling problem
- optimal strategy
- online learning
- initially unknown
- processing times
- learning algorithm
- average case
- worst case
- convergence rate
- upper bound
- release dates
- asymptotically optimal
- resource allocation
- genetic algorithm
- optimal solution
- scheduling algorithm
- linear space
- np hard
- multi agent
- branch and bound algorithm
- decision problems