Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky

Veřejná podpora

  • Poskytovatel

    Grantová agentura České republiky

  • Program

    Standardní projekty

  • Veřejná soutěž

    Standardní projekty 18 (SGA0201400001)

  • Hlavní účastníci

    Masarykova univerzita / Fakulta informatiky

  • Druh soutěže

    VS - Veřejná soutěž

  • Číslo smlouvy

    14-03501S

Alternativní jazyk

  • Název projektu anglicky

    Parameterized algorithms and kernelization in the context of discrete mathematics and logic

  • Anotace anglicky

    A possible approach to overcome the notorious intractability of NP-hard problems is provided by the theory of Parameterized Complexity: an auxiliary "parameter" - an arbitrary number k - is assigned to each input, such that a computable function of k upper-bounds the computational complexity of the problem. The general goal here is to choose a parameter k which attains low values on interesting inputs, thus leading to efficient algorithms on inputs characterized by such k. The project will search for suitable structural and geometric parameters for classes of combinatorial objects (graphs) and use the new findings to obtain more efficient parameterized algorithms, as well as, so-called algorithmic metatheorems based on logic description. In particular, it will continue the recent very successful research of parameterized complexity lower bounds. Metatheorems for kernelization (parameterized preprocessing) of problems, and search for usable geometric parameters (e.g., coming from an input representation of the graph) are specifically mentioned among the new research tasks.

Vědní obory

  • Kategorie VaV

    ZV - Základní výzkum

  • CEP - hlavní obor

    IN - Informatika

  • CEP - vedlejší obor

  • 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>)

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Hodnocení dokončeného projektu

  • Hodnocení poskytovatelem

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

  • Zhodnocení výsledků projektu

    Tým složený ze dvou výzkumníků a dvou PhD studentů výrazně přispěl k řešení problémů ve všech čtyřech plánovaných tématikách. Že tyto výsledky jsou ceněny na mezinárodní úrovni, dosvědčuje následující fakt: tři články byly přijaty na A* konferencích a 5 článků bylo publikováno v prestižních časopisech.

Termíny řešení

  • Zahájení řešení

    1. 1. 2014

  • Ukončení řešení

    31. 12. 2016

  • Poslední stav řešení

    U - Ukončený projekt

  • Poslední uvolnění podpory

    5. 4. 2016

Dodání dat do CEP

  • 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

    CEP17-GA0-GA-U/03:1

  • Datum dodání záznamu

    28. 6. 2017

Finance

  • Celkové uznané náklady

    4 458 tis. Kč

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

    4 458 tis. Kč

  • Ostatní veřejné zdroje financování

    0 tis. Kč

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

    0 tis. Kč