About: Preemptive Online Scheduling: Optimal Algorithms for All Speeds

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Preemptive Online Scheduling: Optimal Algorithms for All Speeds Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	Our main result is an optimal online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize makespan. The algorithm is deterministic, yet it is optimal even among all randomized algorithms. In addition, it is optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various special cases. Together with a new lower bound it follows that the overall competitive ratio of this optimal algorithm is between 2.054 and e approximate to 2.718. Our main result is an optimal online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize makespan. The algorithm is deterministic, yet it is optimal even among all randomized algorithms. In addition, it is optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various special cases. Together with a new lower bound it follows that the overall competitive ratio of this optimal algorithm is between 2.054 and e approximate to 2.718. (en)
Title	Preemptive Online Scheduling: Optimal Algorithms for All Speeds Preemptive Online Scheduling: Optimal Algorithms for All Speeds (en)
skos:prefLabel	Preemptive Online Scheduling: Optimal Algorithms for All Speeds Preemptive Online Scheduling: Optimal Algorithms for All Speeds (en)
skos:notation	RIV/67985840:_____/09:00334960!RIV10-MSM-67985840
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), P(GA201/05/0124), P(IAA1019401), Z(AV0Z10190503)
http://linked.open...iv/cisloPeriodika	4
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Sgall, Jiří Ebenlendr, Tomáš
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Matematický ústav AV ČR, v. v. i.
http://linked.open...dnocenehoVysledku	335563
http://linked.open...ai/riv/idVysledku	RIV/67985840:_____/09:00334960
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	anline algorithms; scheduling (en)
http://linked.open.../riv/klicoveSlovo	scheduling anline algorithms
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[22F0F2DDC512]
http://linked.open...i/riv/nazevZdroje	Algorithmica
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Online algorithms, randomness, and extremal problems Institute for Theoretical Computer Science Theories, proofs and computational complexity
http://linked.open...UplatneniVysledku	2009
http://linked.open...v/svazekPeriodika	53
http://linked.open...iv/tvurceVysledku	Sgall, Jiří Ebenlendr, Tomáš Jawor, W.
http://linked.open...ain/vavai/riv/wos	000264698900005
http://linked.open...n/vavai/riv/zamer	Rozvoj a prohloubení obecných matematických poznatků a jejich užití v dalších vědních oborech a v praxi
issn	0178-4617
number of pages	19 (xsd:int)

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software