Paper Info
Title
A 3/2-approximation algorithm for rate-monotonic multiprocessor scheduling of implicit-deadline tasks
Abstract
We present a new approximation algorithm for rate-monotonic multiprocessor scheduling of periodic tasks with implicit deadlines. We prove that for an arbitrary parameter k ∈ N it yields solutions with at most (3/2 + 1/k)OPT+9k many processors, thus it gives an asymptotic 3/2-approximation algorithm. This improves over the previously best known ratio of 7/4. Our algorithm can be implemented to run in time O(n2), where n is the number of tasks. It is based on custom-tailored weights for the tasks such that a greedy maximal matching and subsequent partitioning by a first-fit strategy yields the result.
Year
Venue
Keywords
2010
WAOA
implicit-deadline task,rate-monotonic multiprocessor scheduling,2-approximation algorithm,implicit deadline,custom-tailored weight,subsequent partitioning,greedy maximal matching,new approximation algorithm,periodic task,arbitrary parameter k,first-fit strategy yield,approximation algorithms,multiprocessor scheduling,scheduling
Field
DocType
Volume
Monotonic function,Approximation algorithm,Mathematical optimization,Multiprocessor scheduling,Fair-share scheduling,Computer science,Scheduling (computing),Matching (graph theory),Periodic graph (geometry)
Conference
6534
ISSN
Citations 
PageRank 
0302-9743
2
0.42
References 
Authors
15
2
Name
Order
Citations
PageRank
Andreas Karrenbauer113320.21
Thomas Rothvoß257033.87