Number of found documents: 23
Published from to

KAM-DIMATIA Series 2005-722 and ITI Series 2005-238
Král´, D.; Tichý, Tomáš; Sgall, Jiří
2005 - English
Článek studuje pravděpodobnostní strategie pro problém plurality. 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. Keywords: concrete complexity; randomized algorithms; aplikovaná matematika; algoritmizace Available at various institutes of the ASCR
KAM-DIMATIA Series 2005-722 and ITI Series 2005-238

Článek studuje pravděpodobnostní strategie pro problém plurality....

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

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

Sgall, Jiří; Feder, T.; Hell, P.; Králď, D.
Matematický ústav, 2004

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
Článek obsahuje jednoduchý kombinatorický důkaaz duality vícecestných toků a řezů. 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. Keywords: maximal flow; minimal cut; duality; finanční toky; teorie toku v sítích 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

Článek obsahuje jednoduchý kombinatorický důkaaz duality vícecestných toků a řezů....

Bagchi, A.; Chaudhary, A.; Kolman, P.; Sgall, Jiří
Matematický ústav, 2004

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
Článek studuje online rozvrhování úloh stejné délky. 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. Keywords: online scheduling; deadlines; randomization; délka; čas 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

Článek studuje online rozvrhování úloh stejné délky....

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

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
Článek navrhuje zlepšené online algoritmy pro správu bufferů v QoS hradlech. 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 --. Keywords: online scheduling; unit jobs; deadlines; algoritmizace; hradla 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

Článek navrhuje zlepšené online algoritmy pro správu bufferů v QoS hradlech....

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

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

Článek studuje složitost dělení dortů....

Sgall, Jiří; Woeginger, G. J.
Matematický ústav, 2004

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
Článek navrhuje zlepšený aproximační algoritmus pro asymetrický problém obchodního cestujícího. 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). Keywords: combinatorial algorithms; graph theory; teorie grafů 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

Článek navrhuje zlepšený aproximační algoritmus pro asymetrický problém obchodního cestujícího....

Blaser, M.; Manthey, B.; Sgall, Jiří
Matematický ústav, 2004

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
Článek dokazuje nemožnost učení neuronů s impulsy. 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. Keywords: neural networks; learning theory; neuronové sítě 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

Článek dokazuje nemožnost učení neuronů s impulsy....

Sgall, Jiří; Šíma, J.
Matematický ústav, 2004

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

Ebenlendr, T.; Sgall, Jiří
Matematický ústav, 2003

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.

Král, D.; Sgall, Jiří
Matematický ústav, 2003

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