KAM-DIMATIA Series 2005-722 and ITI Series 2005-238
Král´, D.; Tichý, Tomáš; Sgall, Jiří
2005 - anglický
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.
Klíčová slova:
concrete complexity; randomized algorithms
Plné texty jsou dostupné na jednotlivých ústavech Akademie věd ČR.
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 - anglický
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ů.
Klíčová slova:
maximal flow; minimal cut; duality
Plné texty jsou dostupné na jednotlivých ústavech Akademie věd ČR.
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 - anglický
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.
Klíčová slova:
online scheduling; deadlines; randomization
Plné texty jsou dostupné na jednotlivých ústavech Akademie věd ČR.
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 - anglický
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.
Klíčová slova:
online scheduling; unit jobs; deadlines
Plné texty jsou dostupné na jednotlivých ústavech Akademie věd ČR.
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 - anglický
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.
Klíčová slova:
combinatorics; graph coloring; homomorphism
Plné texty jsou dostupné na jednotlivých ústavech Akademie věd ČR.
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 - anglický
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ů.
Klíčová slova:
concrete complexity; fair division
Plné texty jsou dostupné na jednotlivých ústavech Akademie věd ČR.
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 - anglický
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.
Klíčová slova:
combinatorial algorithms; graph theory
Plné texty jsou dostupné na jednotlivých ústavech Akademie věd ČR.
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 - anglický
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.
Klíčová slova:
neural networks; learning theory
Plné texty jsou dostupné na jednotlivých ústavech Akademie věd ČR.
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 - anglický
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......
Klíčová slova:
online scheduling; preemption; uniformly related machines
Plné texty jsou dostupné na jednotlivých ústavech Akademie věd ČR.
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 - anglický
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.
Klíčová slova:
graph coloring; list coloring
Plné texty jsou dostupné na jednotlivých ústavech Akademie věd ČR.
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.
NUŠL poskytuje centrální přístup k informacím o šedé literatuře vznikající v ČR v oblastech vědy, výzkumu a vzdělávání. Více informací o šedé literatuře a NUŠL najdete na webu služby.
Vaše náměty a připomínky posílejte na email nusl@techlib.cz
Provozovatel
Zahraniční báze