Inverse 1-median problem on trees under weighted Hamming distance

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 <Subscript>∞</Subscript> 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${\mathcal{NP}}$$</EquationSource> </InlineEquation> -hard. Copyright Springer Science+Business Media, LLC. 2012