Show simple item record

dc.contributor.authorBazgan, Cristina*
dc.contributor.authorToubaline, Sónia*
dc.contributor.authorVanderpooten, Daniel*
dc.date.accessioned2012-03-26T10:04:15Z
dc.date.available2012-03-26T10:04:15Z
dc.date.issued2013
dc.identifier.issn1382-6905
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/8578
dc.language.isoenen
dc.subjectMin edge and node blocker
dc.subjectApproximation
dc.subjectMost vital edges and nodes
dc.subjectp-center
dc.subjectp-median
dc.subjectComplexity
dc.subject.ddc519en
dc.titleComplexity of determining the most vital elements for the p-median and p-center location problems
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe consider the k most vital edges (nodes) and min edge (node) blocker versions of the p-median and p-center location problems. Given a weighted connected graph with distances on edges and weights on nodes, the k most vital edges (nodes) p-median (respectively p-center) problem consists of finding a subset of k edges (nodes) whose removal from the graph leads to an optimal solution for the p-median (respectively p-center) problem with the largest total weighted distance (respectively maximum weighted distance). The complementary problem, min edge (node) blocker p-median (respectively p-center), consists of removing a subset of edges (nodes) of minimum cardinality such that an optimal solution for the p-median (respectively p-center) problem has a total weighted distance (respectively a maximum weighted distance) at least as large as a specified threshold. We show that k most vital edges p-median and k most vital edges p-center are NP-hard to approximate within a factor 57− and 34− respectively, for any ϵ>0, while k most vital nodes p-median and k most vital nodes p-center are NP-hard to approximate within a factor 23−, for any ϵ>0. We also show that the complementary versions of these four problems are NP-hard to approximate within a factor 1.36.
dc.relation.isversionofjnlnameJournal of Combinatorial Optimization
dc.relation.isversionofjnlvol25
dc.relation.isversionofjnlissue2
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages191-207
dc.relation.isversionofdoi10.1007/s10878-012-9469-8
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringer
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-10-06T09:27:28Z
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*
hal.identifierhal-01499692*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record