Title | ||
---|---|---|
Complexity of determining the most vital elements for the p-median and p-center location problems |
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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/s10878-012-9469-8 | J. Comb. Optim. |
Keywords | Field | DocType |
vital element,vital node,vital edge,p-center location problem,optimal solution,min edge,blocker p-median,vital edges p-median,maximum weighted distance,k edge,vital nodes p-median | Graph,Combinatorics,Weighted distance,Mathematical optimization,Cardinality,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
25 | 2 | 1382-6905 |
Citations | PageRank | References |
7 | 0.49 | 7 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Cristina Bazgan | 1 | 679 | 62.76 |
Sonia Toubaline | 2 | 60 | 7.54 |
Daniel Vanderpooten | 3 | 1153 | 74.66 |