Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Algorithms and Complexity for Periodic Real-Time Scheduling

Bonifaci, V., Chan, H.-L., Marchetti-Spaccamela, A., & Megow, N. (2010). Algorithms and Complexity for Periodic Real-Time Scheduling. In M. Charikar (Ed.), 21st Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1350-1359). Philadelphia, PA: SIAM. Retrieved from http://epubs.siam.org/doi/pdf/10.1137/1.9781611973075.109.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
SODA10_109_bonifaciv.pdf (beliebiger Volltext), 760KB
 
Datei-Permalink:
-
Name:
SODA10_109_bonifaciv.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Bonifaci, Vincenzo1, Autor           
Chan, Ho-Leung1, Autor           
Marchetti-Spaccamela, Alberto2, Autor
Megow, Nicole1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We investigate the preemptive scheduling of periodic tasks with hard deadlines. We show that, even in the uniprocessor case, no polynomial time algorithm can test the feasibility of a task system within a constant speedup bound, unless $\ccp=\ccnp$. This result contrasts with recent results for sporadic task systems. For two special cases, synchronous task systems and systems with a constant number of different task types, we provide the first polynomial time constant-speedup feasibility tests for multiprocessor platforms. Furthermore, we show that the problem of testing feasibility is coNP-hard for synchronous multiprocessor tasks systems. The complexity of some of these problems has been open for a long time. We also propose a profit maximization variant of the feasibility problem, where every task has a non-negative profit, and the goal is to find a subset of tasks that can be scheduled feasibly with maximum profit. We give the first constant-speed, constant-approximation algorithm for the case of synchronous task systems, together with related hardness results.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20102010
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 536725
URI: http://epubs.siam.org/doi/pdf/10.1137/1.9781611973075.109
Anderer: Local-ID: C1256428004B93B8-589EFB7CE4CE25C1C12576A70057A553-Bonifaci:2010:b
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 21st Annual ACM-SIAM Symposium on Discrete Algorithms
Veranstaltungsort: Austin (TX), USA
Start-/Enddatum: 2010-01-10 - 2010-01-10

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: 21st Annual ACM-SIAM Symposium on Discrete Algorithms
  Kurztitel : SODA 2010
Genre der Quelle: Konferenzband
 Urheber:
Charikar, Moses, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Philadelphia, PA : SIAM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 1350 - 1359 Identifikator: ISBN: 978-0-898716-98-6