National Repository of Grey Literature 9 records found  Search took 0.01 seconds. 
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áš
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.
Optimal and online preemptive scheduling on uniformly related machines. ITI Series 2003-171
Ebenlendr, T. ; Sgall, Jiří
We consider the problem of preemptive scheduling on uniformly related machines.We present a semi-online algorithm which, if the optimal makespan is given in advance, produces an optimal schedule. Using the standard doubling technique, this yields a 4 competitive deterministic and 2.71 competitive randomized online algorithms. In addition, it matches the performance of the previously......
O nemožnosti učení neuronů s impulsy
Sgall, Jiří ; Šíma, J.
The computational complexity of training a single spiking neuron N with adjustable synaptic delays and binary coded inputs and output is studied. A synchronization technique is introduced so that the results concerning the non-learnability of spiking neurons with binary delays are generalized to arbitrary delays.
O složitosti dělení dortů
Sgall, Jiří ; Woeginger, G. J.
In the cake cutting problem, $n/ge2$ players want to cut a cake into $n$ pieces so that every player gets a ďfairď share of the cake by his own measure. One positive and one negative results are given.
KAM-DIMATIA Series 2004-685 and ITI Series 2004-206. Two algorithms for general list matrix partitions
Sgall, Jiří ; Feder, T. ; Hell, P. ; Králď, D.
List matrix partitions are restricted binary list constraint satisfaction problems which generalize list homomorphisms and many graph partition problems arising, e.g., in the study of perfect graphs. Most of the existing algorithms apply to concrete small matrices, i.e., to partitions problems, provide algorithms for their solution, and discuss their implications.
Zlepšený aproximační algoritmus pro asymetrický problém obchodního cestujícího
Blaser, M. ; Manthey, B. ; Sgall, Jiří
We consider the asymmetric traveling salesperson problem with /gamma-parameterized triangle inequality Chandran and Ram recently gave the first constant factor approximation algorithm with polynomial running time for this problem. We devise an approximation algorithm, which is better than the one of Chandran and Ram for /gamma in [0.5437,1).
Zlepšené online algoritmy pro správu bufferů v QoS hradlech
Chrobak, M. ; Jawor, W. ; Sgall, Jiří ; Tichý, Tomáš
We consider the following buffer management problem arising in QoS networks: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total value of forwarded packets is maximized. If packet is not forwarded before its deadline, it is lost and brings no profit. The main result of the paper is an online 1.939-competitive algorithm --.
Online rozvrhování úloh stejné délky
Chrobak, M. ; Jawor, W. ; Sgall, Jiří ; Tichý, Tomáš
We consider the following scheduling problem. The input is a set of jobs with equal processing times, where each job is specified by its release time and deadline. The goal is to determine a single-processor, non-preemptive schedule of these jobs that maximizes the number of completed jobs. In the online version, each job arrives at its release time.
Jednoduchý kombinatorický důkaz duality vícecestných toků a řezů
Bagchi, A. ; Chaudhary, A. ; Kolman, P. ; Sgall, Jiří
We present a simple combinatorial proof of the duality theorem for multiroute flows and cuts and its corollary which characterizes multiroute flows in termsof classical flows.

Interested in being notified about new results for this query?
Subscribe to the RSS feed.