Improved Minmax Regret 1-Center Algorithms for Cactus Networks with c Cycles
In a facility location problem, if the vertex weights are uncertain one may look for a “robust” solution that minimizes “regret.” We present an O(nlogn) (resp. O(cnlogn)) time algorithm for a tree (resp. c-cycle cactus), where n is the number of vertices
- PDF / 362,075 Bytes
- 12 Pages / 439.363 x 666.131 pts Page_size
- 47 Downloads / 175 Views
2
School of Computing Science, Simon Fraser University, Canada {binay,tiko}@sfu.ca Department of Computer Science, The University of Texas at Austin, USA [email protected]
Abstract. In a facility location problem, if the vertex weights are uncertain one may look for a “robust” solution that minimizes “regret.” We present an O(n log n) (resp. O(cn log n)) time algorithm for a tree (resp. c-cycle cactus), where n is the number of vertices and c is a constant. Our tree algorithm presents an improvement over the previously known algorithms that run in O(n log2 n) time. There is no previously published result tailored specifically for a cactus network. The best algorithm for a general network takes O(mn log n) time, where m is the number of edges.
1
Introduction
Deciding where to locate facilities to minimize the communication or transportation costs is known as the facility location problem. For a recent review of this subject, the reader is referred to [14]. The cost of a vertex is formulated as the distance from the nearest facility weighted by the weight of the vertex. In the “classical” p-center problem, the objective is to find p facility locations such that the maximum cost over all vertices is minimized. This problem has attracted much research interest since the publication of the seminal paper on this topic by Hakimi [13]. It can be applied to the locating of fire stations, distribution centers, etc. Megiddo [16] computed the 1-center of a tree network with non-negative vertex weights in O(n) time, where n is the number of vertices. Megiddo and Tamir also studied this problem [17]. In the minmax regret version of this problem, there is uncertainty in the weights of the vertices and/or edge lengths, and only their ranges are known [11,15]. A particular realization (assignment of a weight to each vertex) is called a scenario. Intuitively, the planner of a facility proposes a location x. Then the adversary finds a scenario that makes x bad (costly), i.e., its “regret” is “deep.” The purpose of the planner is to make this cost as small as possible, no matter which scenario the adversary comes up with. For a general graph with uncertain edge lengths, the minmaxregret 1-center problem was shown to be strongly NP-hard [1]. For a tree, Averbakh and Berman [3] solved the problem in O(n6 ) time, and Burkard and Dollani [8] improved it to O(n3 log n). For a general graph with fixed edge lengths, Averbakh and Berman [2] solved it in O(mn2 log n) time, where m is the number of edges. For a tree A. Pardo and A. Viola (Eds.): LATIN 2014, LNCS 8392, pp. 330–341, 2014. c Springer-Verlag Berlin Heidelberg 2014
Improved Minmax Regret 1-Center Algorithms
331
with fixed edge lengths, they solved the problem in O(n2 ) time [2,3]. For a tree with uncertain edge lengths and uniform vertex weights, they presented an O(n2 log n) time algorithm [3], which was later improved to O(n log n) by Burkard and Dollani [8]. More recently, Yu et al. [19] made further improvements, coming up with more efficient algorithms when the edge lengths a
Data Loading...
