Parameterized shifted combinatorial optimization
The result's identifiers
Result code in 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>
Alternative codes found
RIV/00216224:14330/19:00108272
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Parameterized shifted combinatorial optimization
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Computer and System Sciences
ISSN
0022-0000
e-ISSN
—
Volume of the periodical
99
Issue of the periodical within the volume
99
Country of publishing house
US - UNITED STATES
Number of pages
19
Pages from-to
53-71
UT code for WoS article
000448636500003
EID of the result in the Scopus database
2-s2.0-85054147542