E-viri
Recenzirano
-
Guan, Xiucui; Zhang, Binwu
Journal of global optimization, 09/2012, Letnik: 54, Številka: 1Journal Article
The inverse 1-median problem consists in modifying the weights of the customers at minimum cost such that a prespecified supplier becomes the 1-median of modified location problem. A linear time algorithm is first proposed for the inverse problem under weighted l ∞ norm. Then two polynomial time algorithms with time complexities O ( n log n ) and O ( n ) are given for the problem under weighted bottleneck-Hamming distance, where n is the number of vertices. Finally, the problem under weighted sum-Hamming distance is shown to be equivalent to a 0-1 knapsack problem, and hence is -hard.
