Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorToubaline, Sónia
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2011-03-16T14:37:18Z
dc.date.available2011-03-16T14:37:18Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5766
dc.language.isoenen
dc.subject1-median
dc.subject1-center
dc.subjectcomplexity
dc.subjectmost vital edges and nodes
dc.subjectapproximation
dc.subject.ddc519en
dc.titleComplexity of determining the most vital elements for the 1-median and 1-center location problems
dc.typeCommunication / Conférence
dc.description.abstractenWe consider the k most vital edges (nodes) and min edge (node) blocker versions of the 1-median and 1-center location problems. Given a weighted connected graph with distances on edges and weights on nodes, the k most vital edges (nodes) 1-median (respectively 1-center) problem consists of finding a subset of k edges (nodes) whose removal from the graph leads to an optimal solution for the 1-median (respectively 1-center) problem with the largest total weighted distance (respectively maximum weighted distance). The complementary problem, min edge (node) blocker 1-median (respectively 1-center), consists of removing a subset of edges (nodes) of minimum cardinality such that an optimal solution for the 1-median (respectively 1-center) problem has a total weighted distance spectively a maximum weighted distance) at least as large as a specified threshold. We show that k most vital edges 1-median and k most vital edges 1-center are NP-hard to approximate within a factor 7 − and 4 − respectively, for any > 0, while k most 5 3 vital nodes 1-median and k most vital nodes 1-center are NP-hard to approximate within a factor 3 − , for any > 0. We also show that the 2 complementary versions of these four problems are NP-hard to approx imate within a factor 1.36.
dc.identifier.citationpages237-251
dc.relation.ispartoftitleCombinatorial Optimization and Combinatorial Optimization and Applications4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part I
dc.relation.ispartofeditorWu, Weili
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2010
dc.description.sponsorshipprivateouien
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.ispartofisbn978-3-642-17457-5
dc.relation.confcountryUNITED STATES
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-17458-2_20
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2016-10-06T09:21:11Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record