New challenges in streaming, online, and combinatorial algorithms
Project goals
We propose to study important problems in several areas of theory of algorithms. In streaming algorithms we focus on quantile estimation and on streams of geometric data. In online algorithms we focus on edit distance, throughput scheduling and bin packing. For integer programming we focus on strengthening techniques for block-structured matrices such as proximity scaling. Finally, we propose to study the power of combinatorial algorithms for network flow problems.
Keywords
streaming algorithmsinteger programmingonline algorithmsedit distanceschedulingbin packingnetwork flow
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202400001
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
24-10306S
Alternative language
Project name in Czech
Nové výzvy proudových, online a kombinatorických algoritmů
Annotation in Czech
Navrhujeme studovat důležité problémy v několika oblastech teorie algoritmů. V proudových algoritmech budeme studovat odhady kvantilů a proudy geometrických dat. V online algoritmech se zaměříme na editovací vzdálenost, rozvrhování s maximalizací počtu dokončených úloh, a dále na tzv. bin packing. Pro celočíselné programování se zaměříme na další zlepšení algoritmických technik pro lineární programy s blokovými maticemi. Konečně pro problémy toku v sítích budeme studovat meze použití kombinatorických algoritmů.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
IN - Informatics
Solution timeline
Realization period - beginning
Jan 1, 2024
Realization period - end
Dec 31, 2026
Project status
B - Running multi-year project
Latest support payment
Feb 26, 2024
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
CEP25-GA0-GA-R
Data delivery date
Feb 21, 2025
Finance
Total approved costs
14,122 thou. CZK
Public financial support
12,322 thou. CZK
Other public sources
1,800 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
14 122 CZK thou.
Public support
12 322 CZK thou.
0%
Provider
Czech Science Foundation
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Solution period
01. 01. 2024 - 31. 12. 2026