Type of Publication: | Contribution to a collection |
URI (citable link): | http://nbn-resolving.de/urn:nbn:de:bsz:352-172699 |
Author: | Karrenbauer, Andreas; Rothvoß, Thomas |
Year of publication: | 2011 |
Published in: | Approximation and Online Algorithms / Jansen, Klaus; Solis-Oba, Roberto (ed.). - Berlin, Heidelberg : Springer Berlin Heidelberg, 2011. - (Lecture Notes in Computer Science ; 6534). - pp. 166-177. - ISBN 978-3-642-18317-1 |
DOI (citable link): | https://dx.doi.org/10.1007/978-3-642-18318-8_15 |
Summary: |
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(n 2), 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.
|
Subject (DDC): | 004 Computer Science |
Link to License: | In Copyright |
Bibliography of Konstanz: | Yes |
KARRENBAUER, Andreas, Thomas ROTHVOSS, 2011. A 3/2-approximation algorithm for rate-monotonic multiprocessor scheduling of implicit-deadline tasks. In: JANSEN, Klaus, ed., Roberto SOLIS-OBA, ed.. Approximation and Online Algorithms. Berlin, Heidelberg:Springer Berlin Heidelberg, pp. 166-177. ISBN 978-3-642-18317-1. Available under: doi: 10.1007/978-3-642-18318-8_15
@incollection{Karrenbauer201132app-17269, title={A 3/2-approximation algorithm for rate-monotonic multiprocessor scheduling of implicit-deadline tasks}, year={2011}, doi={10.1007/978-3-642-18318-8_15}, number={6534}, isbn={978-3-642-18317-1}, address={Berlin, Heidelberg}, publisher={Springer Berlin Heidelberg}, series={Lecture Notes in Computer Science}, booktitle={Approximation and Online Algorithms}, pages={166--177}, editor={Jansen, Klaus and Solis-Oba, Roberto}, author={Karrenbauer, Andreas and Rothvoß, Thomas} }
Karrenbauer etal.pdf | 578 |