
Complexity of determining the most vital elements for the p-median and p-center location problems
Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2013), Complexity of determining the most vital elements for the p-median and p-center location problems, Journal of Combinatorial Optimization, 25, 2, p. 191-207. 10.1007/s10878-012-9469-8
View/ Open
Type
Article accepté pour publication ou publiéDate
2013Journal name
Journal of Combinatorial OptimizationVolume
25Number
2Publisher
Springer
Pages
191-207
Publication identifier
Metadata
Show full item recordAuthor(s)
Bazgan, CristinaLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Toubaline, Sónia
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Vanderpooten, Daniel
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We 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.Subjects / Keywords
Min edge and node blocker; Approximation; Most vital edges and nodes; p-center; p-median; ComplexityRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2010) Communication / Conférence
-
Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2012) Article accepté pour publication ou publié
-
Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2011) Communication / Conférence
-
Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié
-
Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié