On-line algorithms and communication complexity
Project goals
This project is a part of basic research in the theory of algorithms and complexity. In the theory of algorithms we focus on solving particular problems of on-line scheduling, e.g., scheduling with possible rejection and scheduling to minimize the l_p norm of the vector of completion times of the machines. We shall also study on-line routing. In complexity theory we shall study the relation of the communication complexity to the rank of the matrix corresponding to the computed function, multi-party communication complexity, and the relation of boolean circuit complexity to communication complexity. In both areas the project follows the current trends of research and builds on the previous work of the participating researchers.
Keywords
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
—
Main participants
Matematický ústav AV ČR, v. v. i.
Contest type
—
Contract ID
—
Alternative language
Project name in Czech
On-line algoritmy a komunikační složitost
Annotation in Czech
Předložený projekt patří do základního výzkumu v teorii algoritmů a teorii složitosti. V teorii algoritmů se zaměříme na řešení konkrétních problémů on-line rozvrhování, např. rozvrhování úloh s možným odmítnutím a rozvrhování s cílem minimalizovat L(p)normu vektoru časů jednotlivých počítačů. Dále se budeme věnovat on-line směrování v sítích. V teorii složitosti budeme studovat vztah komunikační složitosti booleovských obvodů s komunikační složitostí. V obou oblastech se navrhovaný projekt zabývá aktuálními výzkumnými tématy a navazuje na dosavadní práci navrhovatele a garanta projektu.
Scientific branches
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
Údaje řešitele o výsledcích a průběhu projektu a charakteristika výsledků projektu jsou adekvátní. Výstupy projektu jsou co do kvality vysoce nadprůměrné a snesou srovnání s nejlepšími grantovými projekty starších, mezinárodně renomovaných vědeckých prac
Solution timeline
Realization period - beginning
Jan 1, 1997
Realization period - end
Jan 1, 1999
Project status
U - Finished project
Latest support payment
—
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP/2001/GA0/GA01GA/U/N/9:4
Data delivery date
—
Finance
Total approved costs
439 thou. CZK
Public financial support
327 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
439 CZK thou.
Public support
327 CZK thou.
74%
Provider
Czech Science Foundation
CEP
BA - General mathematics
Solution period
01. 01. 1997 - 01. 01. 1999