Modern algorithms: New challenges of complex data sets
Project goals
In this project of basic research we focus on theory of algorithms motivated by complex data sets and networks. In response to the current shift of focus of algorithmic research towards processing and analyzing huge and complex data sets, we shall investigate modern computational models such as streaming and parallel MapReduce algorithms. We shall also consider online and approximation algorithms for scheduling and graph problems; here focus on complex data sets and networks motivates new questions in the area of throughput scheduling, data aggregation and graph problems such as graph coloring, cuts and network flows. The results will be published in high-quality international journals and proceedings of selective conferences in theoretical computer science.
Keywords
theoretical computer sciencealgorithmsbig datastreamingonline algorithmsapproximation algorithmsschedulinggraph algorithms
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 21 (SGA0201700001)
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
17-09142S
Alternative language
Project name in Czech
Moderní algoritmy: Nové výzvy komplexních dat
Annotation in Czech
V tomto projektu základního výzkumu se soustředíme na teorii algoritmů motivovanou komplexními daty a sítěmi. V současné době se do středu zájmu algoritmického výzkumu dostává zpracování a analýza masivních komplexních množin dat. Proto budeme studovat moderní výpočetní modely jako algoritmy pro proudy dat (tzv. streaming) a paralelní algoritmy v modelu MapReduce. Dále budeme studovat online a aproximační algoritmy pro rozvrhování a grafové problémy; zde se soustředíme na nové otázky v oblasti rozvrhování s maximalizací počtu včas rozvržených úloh, v oblasti agregace dat a v grafových problémech jako je barvení grafů, řezy a toky v sítích. Výsledky projektu budou publikovány v kvalitních mezinárodních časopisech a sbornících výběrových konferencí v teoretické informatice.
Scientific branches
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
The project resulted in several basic results in online algorithms, parameterized complexity theory, graph theory, cryptography. Within 3 years, 10 articles in leading journals and 10 papers on top conferences (4x A* and 5x A) were published. A number of students contributed to the results. International cooperation was rich. The financial resources were utilized effectively.
Solution timeline
Realization period - beginning
Jan 1, 2017
Realization period - end
Dec 31, 2019
Project status
U - Finished project
Latest support payment
Apr 3, 2019
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
CEP20-GA0-GA-U/02:1
Data delivery date
Jul 23, 2020
Finance
Total approved costs
7,845 thou. CZK
Public financial support
5,820 thou. CZK
Other public sources
2,025 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
7 845 CZK thou.
Public support
5 820 CZK thou.
74%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2017 - 31. 12. 2019