Back to Search
Start Over
Locating Facilities on a Network to Minimize Their Average Service Radius.
- Source :
- Algorithms & Computation (978-3-540-77118-0); 2007, p587-598, 12p
- Publication Year :
- 2007
-
Abstract
- Let G = (V,E) denote an undirected weighted graph of n nodes and m edges, and let U ⊆ V. The relative eccentricity of a node v ∈ U is the maximum distance in G between v and any other node of U, while the radius of U in G is the minimum relative eccentricity of all the nodes in U. Several facility location problems ask for partitioning the nodes of G so as to minimize some global optimization function of the radii of the subsets of the partition. Here, we focus on the problem of partitioning the nodes of G into exactly p ≥ 2 non-empty subsets, so as to minimize the sum of the subset radii, called the total radius of the partition. This problem can be easily seen to be NP-hard when p is part of the input, but when p is fixed it can be solved in polynomial time by reducing it to a similar partitioning problem. In this paper, we first present an efficient O(n3) time algorithm for the notable case p = 2, which improves the O(mn2 + n3 logn) running time obtainable by applying the aforementioned reduction. Then, in an effort of characterizing meaningful polynomial-time solvable instances of the problem when p is part of the input, we show that (i) when G is a tree, then the problem can be solved in O(n3p3) time, and (ii) when G has bounded treewidth h, then the problem can be solved in O(n4h + 4p3) time. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540771180
- Database :
- Complementary Index
- Journal :
- Algorithms & Computation (978-3-540-77118-0)
- Publication Type :
- Book
- Accession number :
- 34228462
- Full Text :
- https://doi.org/10.1007/978-3-540-77120-3_51