Number of found documents: 17
Published from to

Online competitive algorithms for maximizing weighzed throughput of unit jobs. ITI Series 2003-172
Bartal, Y.; Chin, F. Y. L.; Chrobak, M.; Fung, S. P. Y.; Jawor, W.; Lavi, R.; Sgall, Jiří; Tichý, Tomáš
2003 - English
We study an online buffer management problem for networks supporting Quality-of-Service (QoS) applications, equivalently as an online scheduling problem forunit-length jobs, where each job is specified by its release time, deadline, and a nonnegative weight (QoS value). The goal is to maximize the emph{weighted throughput}, that is the total weight of scheduled jobs. Keywords: scheduling problem; quality-of-service applications Available at various institutes of the ASCR
Online competitive algorithms for maximizing weighzed throughput of unit jobs. ITI Series 2003-172

We study an online buffer management problem for networks supporting Quality-of-Service (QoS) applications, equivalently as an online scheduling problem forunit-length jobs, where each job is ...

Bartal, Y.; Chin, F. Y. L.; Chrobak, M.; Fung, S. P. Y.; Jawor, W.; Lavi, R.; Sgall, Jiří; Tichý, Tomáš
Matematický ústav, 2003

Probabilistic proofs and NP-completeness ( A course on the PCP theorem and itsconsequences )
Sgall, Jiří
2002 - English
Lecture notes. Keywords: computational complexity; approximation algorithms Available at various institutes of the ASCR
Probabilistic proofs and NP-completeness ( A course on the PCP theorem and itsconsequences )

Lecture notes.

Sgall, Jiří
Matematický ústav, 2002

It is tough to be a plumber
Král, D.; Majerech, V.; Sgall, Jiří; Tichý, Tomáš; Woeginger, G.
2002 - English
In the Linux computer game {tt KPlumber/}, the objective is to rotate tiles in a ~ raster of squares so as to complete a~ system of pipes. We give a~complexity classification for the original game and various special cases of it that arise from restting the set of six possible tiles. Keywords: combinatorial games; computational complexity Available at various institutes of the ASCR
It is tough to be a plumber

In the Linux computer game {tt KPlumber/}, the objective is to rotate tiles in a ~ raster of squares so as to complete a~ system of pipes. We give a~complexity classification for the original game and ...

Král, D.; Majerech, V.; Sgall, Jiří; Tichý, Tomáš; Woeginger, G.
Matematický ústav, 2002

Multiprocessor Randomized On-line Scheduling
Tichý, Tomáš
2002 - English
This paper studies randomized on-line non-preemptive scheduling in multiprocessor systems. In this problem each task is specified by its processing time andscheduled on any of $m$ identical processors. The objective is to minimize theexpected mekespan. We prove lemmas and theorems describing $sigma_m$-competitive randomized algorithms on $m$ processors. The main result is an........ Keywords: online; randomized; scheduling Available at various institutes of the ASCR
Multiprocessor Randomized On-line Scheduling

This paper studies randomized on-line non-preemptive scheduling in multiprocessor systems. In this problem each task is specified by its processing time andscheduled on any of $m$ identical ...

Tichý, Tomáš
Matematický ústav, 2002

Analysis of the Harmonic algorithm for three servers
Chrobak, M.; Sgall, Jiří
2002 - English
Harmonic is a randomized $ k $-server algorithm that, at each step, given a request point $ r $, chooses the server to be moved to $ r $ with probability inversely proportional to the distance to $ r $. In this paper we prove that harmonic is $ 6 $-cotitive for $ k = 3 $. Keywords: online algorithms; k-server problem; random walks Available at various institutes of the ASCR
Analysis of the Harmonic algorithm for three servers

Harmonic is a randomized $ k $-server algorithm that, at each step, given a request point $ r $, chooses the server to be moved to $ r $ with probability inversely proportional to the distance to $ r ...

Chrobak, M.; Sgall, Jiří
Matematický ústav, 2002

Semi-online scheduling with decreasing job sizes
Seiden, S.; Sgall, Jiří; Woeginger, G.W.
1998 - English
Available at various institutes of the ASCR
Semi-online scheduling with decreasing job sizes

Seiden, S.; Sgall, Jiří; Woeginger, G.W.
Matematický ústav, 1998

Approximation schemes for scheduling on uniformly related and identical parallel machines
Epstein, L.; Sgall, Jiří
1998 - English
Available at various institutes of the ASCR
Approximation schemes for scheduling on uniformly related and identical parallel machines

Epstein, L.; Sgall, Jiří
Matematický ústav, 1998

About project

NRGL provides central access to information on grey literature produced in the Czech Republic in the fields of science, research and education. You can find more information about grey literature and NRGL at service web

Send your suggestions and comments to nusl@techlib.cz

Provider

http://www.techlib.cz

Facebook

Other bases