All
All

What are you looking for?

All
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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

  • R&D category

  • CEP classification - main branch

    BA - General mathematics

  • CEP - secondary branch

  • CEP - another secondary branch

  • 10101 - Pure mathematics

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