FIT - Melissinos, Nikolaos
Program
CTU Global Postdoc Fellowship
Period
2022 - 2024
Description
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.
New Frontiers in Computational Social Choice
Program
Standard projects
Provider
Czech Science Foundation
Departments
Investigators
Code
GA22-19557S
Period
2022 - 2024
Description
Fixed-parameter tractability and approximation algorithms are nowadays standard tools for design of algorithms for hard problems in the area of Computational Social Choice. Surprisingly, kernelization, a prominent technique in FPT algorithmics, is not used as often to tackle social choice problems. Kernelization is a formalism of safe data reduction which we believe does have its place in all research disciplines dealing with large and complex datasets. The most recent approach is the so-called lossy kernelization which on the one hand cooperates with approximation algorithms (unlike kernelization which can only be pipelined with exact algorithms) and on the other hand, allows circumventing hardness results (in exchange for introducing a possible loss in the quality of the solution). This project aims on filling this gap of usage of these tools in computational social choice. The suggested line of research continues our current studies in this area and the new proposed directions will need novel algorithmic approaches as they focus on the boundaries of traceability.
We have identified several interesting questions where there is potential to apply the above. Our aim is to significantly deepen our understanding of these computationally hard problems by providing polynomial-sized (lossy) kernels or showing that the problems are resistant to this line of attack.
Parameterized Algorithms for Fundamental Network Problems Related to Connectivity
Program
Post-graduate (doctorate) grants
Provider
Czech Science Foundation
Departments
Investigators
Code
GP14-13017P
Period
2014 - 2016
Description
Parameterized algorithmics became in the last two decades a standard tool to solve computationally hard (NP-hard) problems. The running time here is expressed in terms of a secondary measure (the parameter) additionally to the input size, which provides a more refined analysis of where the hardness of the problem comes from. 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. In this research proposal we plan to study several open questions related to fundamental problems in the field of network design within the framework of parameterized complexity. More precisely, we will focus on the following two areas: Steiner-type problems in graphs; Network Measurement, Navigation, and Resource Placement. We plan to provide a systematic multivariate complexity analysis, which we feel is missing in the area.
STIGMA - School on Theoretical Informatics, Graphs and Mathematical Applications
Program
Studentská vědecká konference ČVUT
Departments
Investigators
Code
SVK 57/16/F8
Period
2016
Description
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
Departments
Investigators
Code
SVK 49/15/F8
Period
2015
Description
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.
Structural Approaches in Stability Under Diversity Constraints
Program
Promoting the mobility of researchers and workers in the framework of international cooperation in R&D
Provider
Ministry of Education, Youth and Sports
Investigators
Code
8J21AT021
Period
2021 - 2022
Description
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ě.
Tight Parameterized Results for Directed Connectivity Problems
Program
Standard projects
Provider
Czech Science Foundation
Departments
Investigators
Code
GA17-20065S
Period
2017 - 2019
Description
A 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.
Recently, more focus is put on achieving the best possible polynomial degree as well as the best asymptotic time dependency on the parameter. This is justified by providing matching lower bounds, showing that the existence of significantly faster algorithms is improbable, typically relying on the Exponential Time Hypothesis or its strong form.
In this research proposal we target on several fundamental problems in network design related to connectivity in directed graphs from the parameterized perspective. Our aim is to either obtain new algorithms for the problems with better running time than that of the existing algorithms, or to obtain lower bounds showing that such an improvement is unlikely.
Our main focus are Steiner-type problems in directed graphs.