Parameterized Shifted Combinatorial Optimization
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F17%3A00095083" target="_blank" >RIV/00216224:14330/17:00095083 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-319-62389-4_19" target="_blank" >http://dx.doi.org/10.1007/978-3-319-62389-4_19</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-62389-4_19" target="_blank" >10.1007/978-3-319-62389-4_19</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Parameterized Shifted Combinatorial Optimization
Popis výsledku v původním jazyce
Shifted combinatorial optimization is a new nonlinear optimization framework which is a broad extension of standard combinatorial optimization, involving the choice of several feasible solutions at a time. This framework captures well studied and diverse problems ranging from so-called vulnerability problems to sharing and partitioning problems. In particular, every standard combinatorial optimization problem has its shifted counterpart, which is typically much harder. Already with explicitly given input set the shifted problem may be NP-hard. In this article we initiate a study of the parameterized complexity of this framework. First we show that shifting over an explicitly given set with its cardinality as the parameter may be in XP, FPT or P, depending on the objective function. Second, we study the shifted problem over sets definable in MSO logic (which includes, e.g., the well known MSO partitioning problems). Our main results here are that shifted combinatorial optimization over MSO definable sets is in XP with respect to the MSO formula and the treewidth (or more generally clique-width) of the input graph, and is W[1]-hard even under further severe restrictions.
Název v anglickém jazyce
Parameterized Shifted Combinatorial Optimization
Popis výsledku anglicky
Shifted combinatorial optimization is a new nonlinear optimization framework which is a broad extension of standard combinatorial optimization, involving the choice of several feasible solutions at a time. This framework captures well studied and diverse problems ranging from so-called vulnerability problems to sharing and partitioning problems. In particular, every standard combinatorial optimization problem has its shifted counterpart, which is typically much harder. Already with explicitly given input set the shifted problem may be NP-hard. In this article we initiate a study of the parameterized complexity of this framework. First we show that shifting over an explicitly given set with its cardinality as the parameter may be in XP, FPT or P, depending on the objective function. Second, we study the shifted problem over sets definable in MSO logic (which includes, e.g., the well known MSO partitioning problems). Our main results here are that shifted combinatorial optimization over MSO definable sets is in XP with respect to the MSO formula and the treewidth (or more generally clique-width) of the input graph, and is W[1]-hard even under further severe restrictions.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2017
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
International Computing and Combinatorics Conference COCOON 2017 (LNCS, volume 10392)
ISBN
9783319623887
ISSN
—
e-ISSN
—
Počet stran výsledku
13
Strana od-do
224-236
Název nakladatele
Springer International Publishing AG
Místo vydání
Hong Kong
Místo konání akce
Hong Kong
Datum konání akce
3. 8. 2017
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000771461800019