Restricted computations: Algorithms, models, complexity
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 18 (SGA0201400001)
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
14-10003S
Alternative language
Project name in Czech
Omezené typy výpočtů: algoritmy, modely, složitost
Annotation in Czech
V tomto projektu základního výzkumu se soustředíme na roli omezených typů výpočtů v teorii složitosti a v teorii algoritmů. Budeme studovat problémy, pro které zkoumání omezených typů výpočtů může vést k podstatně silnějším a těsnějším dolním a horním odhadům složitosti a kvality algoritmů ve srovnání s tradičním studiem neomezených výpočtů. Ve výpočetní složitosti budeme studovat kombinatorické algoritmy pro problémy jako násobení booleovských matic a 3SUM, což je omezená varianta problému hledání podmnožiny s daným součtem. V algoritmické části projektu se zaměříme na online a aproximační algoritmy pro omezené varianty problému bin packing s omezeným prostorem, rozvrhování s cílem maximalizovat cenu splněných úloh a toky s omezenou délkou.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
—
CEP - another secondary branch
—
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
The project brought some truly excellent scientific advances (despite one key member concurrently worked on his ERC grant), and more high quality outcomes on international level. We specially mention top-ranking conferences STOC, SODA and ESA. Advances have been achieved in all areas of the proposal and, moreover, in additional direction of streaming algorithms.
Solution timeline
Realization period - beginning
Jan 1, 2014
Realization period - end
Dec 31, 2016
Project status
U - Finished project
Latest support payment
Apr 12, 2016
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
CEP17-GA0-GA-U/03:1
Data delivery date
Jun 28, 2017
Finance
Total approved costs
4,300 thou. CZK
Public financial support
4,300 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK