Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks
 
conference paper

A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks

Karrenbauer, Andreas
•
Rothvoss, Thomas  
2011
Approximation and Online Algorithms, 8th International Workshop (WAOA 2010)
Approximation and Online Algorithms, 8th International Workshop (WAOA 2010)

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 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.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-642-18318-8_15
Author(s)
Karrenbauer, Andreas
Rothvoss, Thomas  
Date Issued

2011

Publisher

Springer

Published in
Approximation and Online Algorithms, 8th International Workshop (WAOA 2010)
Series title/Series vol.

Lecture Notes in Computer Science; 6534

Start page

166

End page

177

Subjects

scheduling

•

approximation algorithms

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Event nameEvent placeEvent date
Approximation and Online Algorithms, 8th International Workshop (WAOA 2010)

Liverpool, UK

September 9-10, 2010

Available on Infoscience
November 21, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/58001
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés