**17**

###
**KAM-DIMATIA Series 2005-722 and ITI Series 2005-238**

Král´, D.; Tichý, Tomáš; Sgall, Jiří

2005 - English
We give asymptotically tight bounds both for randomized algorithms for the plurality problem in the case of two colors and many colors. For the balls colored by $k$ colors, we prove a lower bound $/Omega(kn)$ on the expected number of questions. Článek studuje pravděpodobnostní strategie pro problém plurality.
Keywords:
*concrete complexity; randomized algorithms*
Available at various institutes of the ASCR
KAM-DIMATIA Series 2005-722 and ITI Series 2005-238

We give asymptotically tight bounds both for randomized algorithms for the plurality problem in the case of two colors and many colors. For the balls colored by $k$ colors, we prove a lower bound ...

###
**KAM-DIMATA Series 2004-662 and ITI Series 2004-186. A simple combinatorial proof of duality of multiroute flows and cuts**

Bagchi, A.; Chaudhary, A.; Kolman, P.; Sgall, Jiří

2004 - English
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. Článek obsahuje jednoduchý kombinatorický důkaaz duality vícecestných toků a řezů.
Keywords:
*maximal flow; minimal cut; duality*
Available at various institutes of the ASCR
KAM-DIMATA Series 2004-662 and ITI Series 2004-186. A simple combinatorial proof of duality of multiroute flows and cuts

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

###
**KAM-DIMATA Series 2004-659 and ITI Series 2004-182. Online scheduling of equal-length jobs: Randomization and restarts help**

Chrobak, M.; Jawor, W.; Sgall, Jiří; Tichý, Tomáš

2004 - English
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. Článek studuje online rozvrhování úloh stejné délky.
Keywords:
*online scheduling; deadlines; randomization*
Available at various institutes of the ASCR
KAM-DIMATA Series 2004-659 and ITI Series 2004-182. Online scheduling of equal-length jobs: Randomization and restarts help

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

###
**KAM-DIMATA Series 2004-658 and ITI Series 2004-181. Improved online algorithms for buffer management in QoS switches**

Chrobak, M.; Jawor, W.; Sgall, Jiří; Tichý, Tomáš

2004 - English
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 --. Článek navrhuje zlepšené online algoritmy pro správu bufferů v QoS hradlech.
Keywords:
*online scheduling; unit jobs; deadlines*
Available at various institutes of the ASCR
KAM-DIMATA Series 2004-658 and ITI Series 2004-181. Improved online algorithms for buffer management in QoS switches

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

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

2004 - English
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.
Keywords:
*combinatorics; graph coloring; homomorphism*
Available at various institutes of the ASCR
KAM-DIMATIA Series 2004-685 and ITI Series 2004-206. Two algorithms for general list matrix partitions

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

###
**KAM-DIMATIA Series 2004-688 and ITI Series 2004-208. On the complexity of cake cutting**

Sgall, Jiří; Woeginger, G. J.

2004 - English
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. Článek studuje složitost dělení dortů.
Keywords:
*concrete complexity; fair division*
Available at various institutes of the ASCR
KAM-DIMATIA Series 2004-688 and ITI Series 2004-208. On the complexity of cake cutting

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

###
**KAM-DIMATA Series 2004-657 and ITI Series 2004-180. An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality**

Blaser, M.; Manthey, B.; Sgall, Jiří

2004 - English
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). Článek navrhuje zlepšený aproximační algoritmus pro asymetrický problém obchodního cestujícího.
Keywords:
*combinatorial algorithms; graph theory*
Available at various institutes of the ASCR
KAM-DIMATA Series 2004-657 and ITI Series 2004-180. An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality

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

###
**KAM-DIMATIA Series 2004-695 and ITI Series 2004-216. On the Non-Learnability of a Single Spiking Neuron**

Sgall, Jiří; Šíma, J.

2004 - English
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. Článek dokazuje nemožnost učení neuronů s impulsy.
Keywords:
*neural networks; learning theory*
Available at various institutes of the ASCR
KAM-DIMATIA Series 2004-695 and ITI Series 2004-216. On the Non-Learnability of a Single Spiking Neuron

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

###
**Optimal and online preemptive scheduling on uniformly related machines. ITI Series 2003-171**

Ebenlendr, T.; Sgall, Jiří

2003 - English
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......
Keywords:
*online scheduling; preemption; uniformly related machines*
Available at various institutes of the ASCR
Optimal and online preemptive scheduling on uniformly related machines. ITI Series 2003-171

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

###
**Coloring graphs from lists with bounded size of their union. KAM-DIMATIA. Series 2003-641 and ITI Series 2003-156**

Král, D.; Sgall, Jiří

2003 - English
We construct a graph G which is k-choosable from any lists of colors whoseunion has size at most u but the same does not hold with lists whose union has size u+1.
Keywords:
*graph coloring; list coloring*
Available at various institutes of the ASCR
Coloring graphs from lists with bounded size of their union. KAM-DIMATIA. Series 2003-641 and ITI Series 2003-156

We construct a graph G which is k-choosable from any lists of colors whoseunion has size at most u but the same does not hold with lists whose union has size u+1.

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