Vis enkel innførsel

dc.contributor.authorFomin, Fedor
dc.contributor.authorRamamoorthi, Vijayaragunathan
dc.date.accessioned2022-11-07T13:38:45Z
dc.date.available2022-11-07T13:38:45Z
dc.date.created2022-06-01T12:16:13Z
dc.date.issued2022
dc.identifier.issn1432-4350
dc.identifier.urihttps://hdl.handle.net/11250/3030470
dc.description.abstractThe MAXIMUM COVERING LOCATION PROBLEM (MCLP) is a well-studied problem in the field of operations research. Given a network with positive or negative demands on the nodes, a positive integer k, the MCLP seeks to find k potential facility centers in the network such that the neighborhood coverage is maximized. We study the variant of MCLP where edges of the network are subject to random failures due to some disruptive events. One of the popular models capturing the unreliable nature of the facility location is the linear reliability ordering (LRO) model. In this model, with every edge e of the network, we associate its survival probability 0 ≤ pe ≤ 1, or equivalently, its failure probability 1 − pe. The failure correlation in LRO is the following: If an edge e fails then every edge e′ with pe′≤pe surely fails. The task is to identify the positions of k facilities that maximize the expected coverage. We refer to this problem as EXPECTED COVERAGE problem. We study the EXPECTED COVERAGE problem from the parameterized complexity perspective and obtain the following results. 1. For the parameter pathwidth, we show that the EXPECTED COVERAGE problem is W[1]-hard. We find this result a bit surprising, because the variant of the problem with non-negative demands is fixed-parameter tractable (FPT) parameterized by the treewidth of the input graph. 2. We complement the lower bound by the proof that EXPECTED COVERAGE is FPT being parameterized by the treewidth and the maximum vertex degree. We give an algorithm that solves the problem in time 2O(twlogΔ)nO(1), where tw is the treewidth, Δ is the maximum vertex degree, and n the number of vertices of the input graph. In particular, since Δ ≤ n, it means the problem is solvable in time nO(tw), that is, is in XP parameterized by treewidth.en_US
dc.language.isoengen_US
dc.publisherSpringeren_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/deed.no*
dc.titleOn the Parameterized Complexity of the Expected Coverage Problemen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright 2022 The Author(s)en_US
cristin.ispublishedtrue
cristin.fulltextoriginal
cristin.qualitycode1
dc.identifier.doi10.1007/s00224-022-10073-0
dc.identifier.cristin2028710
dc.source.journalTheory of Computing Systemsen_US
dc.source.pagenumber432-453en_US
dc.relation.projectNorges forskningsråd: 314528en_US
dc.identifier.citationTheory of Computing Systems. 2022, 66, 432-453.en_US
dc.source.volume66en_US


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Navngivelse 4.0 Internasjonal
Med mindre annet er angitt, så er denne innførselen lisensiert som Navngivelse 4.0 Internasjonal