No (17)
Used filters
(3)
Number of found documents:
17
Published from
to
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