FIT - Melissinos, Nikolaos
Program
CTU Global Postdoc Fellowship
Období
2022 - 2024
Popis
Parameterized or multivariate analysis became in the last two decades a standard approach for (NP-) hard computational problems. Here, in contrast to classical complexity, the efficiency of algorithms is not measured only with respect to the length of the input instance, but also with respect to a specified parameter. The outcome is a more fine grained complexity landscape which allows for a better prediction of the complexity of particular instances encountered. The goal is to design algorithms with running time that is polynomial in the input size and exponential only in the designated parameter. Fundamentally, the degree of the polynomial is required to be independent of the value of the parameter. Parameterized complexity provides a mathematical framework to analyze these algorithms and also to show that for some problems and parameters there is (probably) no such algorithm.
Nové výzvy ve výpočetní sociální volbě
Program
Standardní projekty
Poskytovatel
Grantová agentura České republiky
Pracoviště
Řešitelé
Kód
GA22-19557S
Období
2022 - 2024
Popis
Pro návrh algoritmů na řešení těžkých problémů v oblasti výpočetní sociální volby jsou dnes standardem jak parametrizované tak aproximační algoritmy. Kernelizace, jedna z hlavních technik v parametrizované složitosti, je překvapivě málo používána pro řešení problémů sociální volby. Jsme přesvědčeni, že kernelizace -- formalismus pro bezpečnou redukci vstupních dat -- má své místo ve všech výzkumných odvětvích týkajících se velkých vstupních dat. Nejnovějšı́ koncept je tzv. ztrátová kernelizace, která je jednak použitelná v kombinaci s aproximačními algoritmy (narozdíl od normální kernelizace, kterou lze kombinovat pouze s exaktními algoritmy), a druhak dokáže obejít těžkostní výsledky za cenu zavedení mírné nepřesnosti do výsledku. Navrhujeme aplikovat tyto moderní nástroje -- ztrátovou kernelizaci -- ve výpočetní sociální volbě. Navrhovaný projekt navazuje na naši předchozí práci v tomto oboru a uvažované směřování výzkumu bude vyžadovat nové algoritmické přı́stupy.
Vytipovali jsme řadu zajímavých otevřených problémů a otázek, kde vidíme potenciál dosáhnout výsledků aplikováním zmíněných technik. Cílem je významně prohloubit poznání výpočetní složitosti těchto problémů nalezením polynomiálně velkých (ztrátových) kernelů popřípadě vyloučit jejich existenci.
Parametrizované algoritmy pro základní síťové problémy spojené se souvislostí
Program
Postdoktorandské granty
Poskytovatel
Grantová agentura České republiky
Pracoviště
Řešitelé
Kód
GP14-13017P
Období
2014 - 2016
Popis
Parametrizované algoritmy se staly v posledních dvou dekádách standardním nástrojem pro řešení výpočetně těžkých (NP-těžkých) problémů. Časová složitost se v tomto vyjadřuje pomocí druhotné míry (parametru) navíc k velikosti vstupu, čímž se dosahuje jemnější analýza původu těžkosti problému. Parametrizovaná složitost představuje matematický rámec pro analyzování takových algoritmů a také umožnuje ukázat, že pro některé problémy a parametry (pravděpodobně) žádný takový algoritmus neexistuje. V rámci toho projektu plánujeme studovat některé otevřené otázky související se základními problémy v oblasti návrhu sítí z pohledu parametrizované složitosti. Přesněji se zaměříme na tyto dvě oblasti: problémy Steinerovského typu v grafech a měření, navigace a umístění zdrojů v sítích. Plánujeme připravit systematickou multivarietní analýzu, která podle našeho názoru v této oblasti chybí.
STIGMA - School on Theoretical Informatics, Graphs and Mathematical Applications
Program
Studentská vědecká konference ČVUT
Pracoviště
Řešitelé
Kód
SVK 57/16/F8
Období
2016
Popis
Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům
prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost
naučit se novým technikám a postupům z aktuálních vědeckých výsledků,
nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy,
a v neposlední řadě též příležitost navázat mezi sebou kontakty.
Během dne proběhne několik přednáškových bloků.
Zbývající čas je vyhrazen na řešení problémů a diskuze.
Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu,
nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference.
Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty
k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení.
Tématicky je konference vymezena na tyto oblasti:
- teoretická informatika
- diskrétní matematika
- teorie grafů
- výpočetní složitost a algoritmy
- datové struktury
Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.
STIGMA - School on Theoretical Informatics, Graphs and MAthematics
Program
Studentská vědecká konference ČVUT
Pracoviště
Řešitelé
Kód
SVK 49/15/F8
Období
2015
Popis
Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům
prostor pro prezentaci jejich vědecké práce a činnosti mezi s sebou, příležitost
naučit se novým technikám a postupům z aktuálních vědeckých výsledků,
nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy,
a v neposlední řadě též příležitost navázat mezi sebou kontakty.
Během dne proběhne několik přednáškových bloků.
Zbývající čas je vyhrazen na řešení problémů a diskuze.
Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu,
nebo aktuálního vědeckého výsledku zapadajícího do tematiky konference.
Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty
k budoucímu výzkumu a nabídnou tak vhodné problémy.
Tematicky je konference vymezena na tato témata:
- teoretická informatika
- diskrétní matematika
- teorie grafů a grafové algoritmy
- výpočetní složitost a algoritmy
Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.
Strukturální přístup pro různorodost stabilních řešení
Program
Podpora mobility výzkumných pracovníků a pracovnic v rámci mezinárodní spolupráce ve VaVaI
Poskytovatel
Ministerstvo školství, mládeže a tělovýchovy
Řešitelé
Kód
8J21AT021
Období
2021 - 2022
Popis
Výpočetní kolektivní volba (Computational Social Choice) je moderní oblast informatiky, ve které se setkává teoretická informatika a teorie her (ekonomie). Mnoho zásadních problémů v této oblasti je NP-těžkých, proto se začala v poslední dekádě stále častěji uplatňovat tzv. parametrizovaná analýza, která si klade za cíl identifikovat parametry, jejichž zafixování na malých hodnotách vede k efektivní řešitelnosti daného problému. V předkládaném projektu se hodláme zaměřit na strukturální parametry (mezi nejznámější bezpochyby patří stromová šířka) vstupních instancí, čímž omezíme například vzájemnou interakci mezi agenty hledajícími kolektivní rozhodnutí a podobně.
Těsné parametrizované výsledky pro problémy orientované souvislosti
Program
Standardní projekty
Poskytovatel
Grantová agentura České republiky
Pracoviště
Řešitelé
Kód
GA17-20065S
Období
2017 - 2019
Popis
Parametrizovaná nebo multivarietní analýza se v minulých dvou dekádách stala standardním
přístupem k (NP-) těžkým problémům. Oproti klasické výpočetní složitosti se zde efektivita
algoritmů měří nejen vzhledem k délce vstupu, ale také vzhledem k určenému parametru.
V poslední době je kladen větší důraz na získání nejlepšího možného stupně polynomu stejně
jako nejlepší asymptotické závislosti na parametru. To je prokázáno předvedením dolních mezí
ukazujících, že existence výrazně rychlejších algoritmů je nepravděpodobná, typicky založených
na hypotéze exponenciálního času, nebo její silné formě.
V tomto návrhu projektu se zaměřujeme na několik zásadních problémů v návrhu sítí spojených
se souvislostí v orientovaných grafech z parametrizovaného pohledu. Náš cíl je získat nové
algoritmy pro tyto problémy s lepší časovou složitostí než mají existující algoritmy, nebo získat
dolní meze ukazující, že takové vylepšení je nepravděpodobné. Naším hlavním zaměřením jsou
problémy Steinerovského typu na orientovaných grafech.