Complexity of determining the most vital elements for the p-median and p-center location problems

Cristina Bazgan (), Sonia Toubaline () and Daniel Vanderpooten ()
Additional contact information
Cristina Bazgan: Université Paris-Dauphine
Sonia Toubaline: Université Paris-Dauphine
Daniel Vanderpooten: Université Paris-Dauphine

Journal of Combinatorial Optimization, 2013, vol. 25, issue 2, No 3, 207 pages

Abstract: Abstract 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 $\frac{7}{5}-\epsilon$ and $\frac{4}{3}-\epsilon$ 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 $\frac{3}{2}-\epsilon$ , for any ϵ>0. We also show that the complementary versions of these four problems are NP-hard to approximate within a factor 1.36.

Keywords: Most vital edges and nodes; Min edge and node blocker; p-median; p-center; Complexity; Approximation (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9469-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:25:y:2013:i:2:d:10.1007_s10878-012-9469-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9469-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().