Nové kombinatorické algoritmy - rozklady instancí, parametry úloh a jejich efektivní řešení

Poskytovatel

Ministerstvo školství, mládeže a tělovýchovy

Program

KONTAKT II

Veřejná soutěž

KONTAKT II 2 (SMSM2012LH2)

Hlavní účastníci

Univerzita Karlova / Matematicko-fyzikální fakulta

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

MSMT-6805/2013-311

Název projektu anglicky

New combinatorial algorithms - decompositions, parameterization, efficient solutions

Anotace anglicky

The project brings new mathematical results concerning optimizing combinatorial problems. As a necessary requirement for the development of efficient algorithms the project focuses on structural dependencies of the studied problems in terms of graph decompositions and various structural parameters. The studied dependency of the solution of the problem on parameters will be a core clue for the design of algorithms. These algorithms will have polynomial running time, if possible, or alternatively the running time will be exponential but with smallest possible base of the exponent (so called fast exponential algorithms). The problems will be chosen from the area of telecommunication, transport and resource management.

Kategorie VaV

ZV - Základní výzkum

CEP - hlavní obor

BA - Obecná matematika

CEP - vedlejší obor

IN - Informatika

CEP - další vedlejší obor

—

OECD FORD - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

10101 - Pure mathematics<br>10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Hodnocení poskytovatelem

V - Vynikající výsledky projektu (s mezinárodním významem atd.)

Zhodnocení výsledků projektu

V rámci společného výzkumného projektu NewAlgo - Nové kombinatorické algoritmy, zorganizovaného Univerzitou Karlovou v Praze, University of Oregon v Eugene a Gorgia Institiute of Technology v Atlantě získlai vvědci teoretické poznatky z oblasti kombinatorické optimalizace např. o barevnosti grafů či o hledání hamiltonovských cest v grafech.

Zahájení řešení

1. 3. 2012

Ukončení řešení

31. 12. 2015

Poslední stav řešení

U - Ukončený projekt

Poslední uvolnění podpory

27. 2. 2015

Důvěrnost údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Systémové označení dodávky dat

CEP16-MSM-LH-U/01:1

Datum dodání záznamu

9. 10. 2017

Celkové uznané náklady

1 967 tis. Kč

Výše podpory ze státního rozpočtu

1 767 tis. Kč

Ostatní veřejné zdroje financování

200 tis. Kč

Neveřejné tuz. a zahr. zdroje finan.

0 tis. Kč