Computer Science – Data Structures and Algorithms
Scientific paper
2012-04-04
Computer Science
Data Structures and Algorithms
Scientific paper
We propose a new approach to competitive analysis in online scheduling by introducing the novel concept of online approximation schemes. Such a scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily close to the best possible competitive ratio for any online algorithm. We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines, and we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. We also general- ize our techniques to arbitrary monomial cost functions and apply them to the makespan objective. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations. We also contribute algorithmic means to compute the actual value of the best possi- ble competitive ratio up to an arbitrary accuracy. This strongly contrasts all previous manually obtained competitiveness results for algorithms and, most importantly, it reduces the search for the optimal com- petitive ratio to a question that a computer can answer. We believe that our concept can also be applied to many other problems and yields a new perspective on online algorithms in general.
Günther Elisabeth
Maurer Olaf
Megow Nicole
Wiese Andreas
No associations
LandOfFree
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-31823