**17**

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

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

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

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

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

###
**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

###
**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

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

Other bases