Parameterized shifted combinatorial optimization

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10386782" target="_blank" >RIV/00216208:11320/19:10386782 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216224:14330/19:00108272

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=aC_6IblCOe" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=aC_6IblCOe</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jcss.2018.06.002" target="_blank" >10.1016/j.jcss.2018.06.002</a>

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 broadly extending standard combinatorial optimization, involving the choice of several feasible solutions simultaneously. This framework captures well studied and diverse problems, from sharing and partitioning to so-called vulnerability problems. In particular, every standard combinatorial optimization problem has its shifted counterpart, typically harder. Already with explicitly given input set SCO may be NP-hard. Here we initiate a study of the parameterized complexity of this framework. First we show that SCO over an explicitly given set parameterized by its cardinality may be in XP, FPT or P, depending on the objective function. Second, we study SCO over sets definable in MSO logic (which includes, e.g., the well known MSO-partitioning problems). Our main results are that SCO over MSO definable sets is in XP parameterized by the MSO formula and treewidth (or clique-width) of the input graph, and W[1]-hard even under further severe restrictions. (C) 2018 Elsevier Inc. All rights reserved.

Název v anglickém jazyce

Parameterized shifted combinatorial optimization

Popis výsledku anglicky

Shifted combinatorial optimization is a new nonlinear optimization framework broadly extending standard combinatorial optimization, involving the choice of several feasible solutions simultaneously. This framework captures well studied and diverse problems, from sharing and partitioning to so-called vulnerability problems. In particular, every standard combinatorial optimization problem has its shifted counterpart, typically harder. Already with explicitly given input set SCO may be NP-hard. Here we initiate a study of the parameterized complexity of this framework. First we show that SCO over an explicitly given set parameterized by its cardinality may be in XP, FPT or P, depending on the objective function. Second, we study SCO over sets definable in MSO logic (which includes, e.g., the well known MSO-partitioning problems). Our main results are that SCO over MSO definable sets is in XP parameterized by the MSO formula and treewidth (or clique-width) of the input graph, and W[1]-hard even under further severe restrictions. (C) 2018 Elsevier Inc. All rights reserved.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

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ů

Název periodika

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

—

Svazek periodika

99

Číslo periodika v rámci svazku

99

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

19

Strana od-do

53-71

Kód UT WoS článku

000448636500003

EID výsledku v databázi Scopus

2-s2.0-85054147542