Title | ||
---|---|---|
Complexity of determining the most vital elements for the 1-median and 1-center location problems |
Abstract | ||
---|---|---|
We 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 (respectively 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/5 - ε and 4/3 - ε respectively, for any ε 0, while k most vital nodes 1-median and k most vital nodes 1-center are NP-hard to approximate within a factor 3/2 - ε, 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 | Venue | Keywords |
---|---|---|
2010 | conference on combinatorial optimization and applications | 1-center location problem,vital element,vital node,vital edge,optimal solution,min edge,vital nodes 1-center,maximum weighted distance,k edge,vital edges 1-center,blocker 1-median,approximation,complexity,connected graph |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Weighted distance,Cardinality,Connectivity,Multiple edges,Mathematics | Conference | 6508 |
ISSN | ISBN | Citations |
0302-9743 | 3-642-17457-4 | 5 |
PageRank | References | Authors |
0.46 | 7 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Cristina Bazgan | 1 | 679 | 62.76 |
Sonia Toubaline | 2 | 60 | 7.54 |
Daniel Vanderpooten | 3 | 1153 | 74.66 |