Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information.
Yiwei JiangYong HePublished in: Acta Informatica (2007)
Keyphrases
- competitive ratio
- partial information
- scheduling problem
- single machine
- online algorithms
- processing times
- lower bound
- worst case
- incomplete information
- average case
- np hard
- optimal strategy
- dynamic programming
- online learning
- flowshop
- learning algorithm
- asymptotically optimal
- completion times
- uniform distribution
- multi agent