哈明距离下1-重心问题的反问题

摘要

This paper mainly discusses the reverse 1-median problem under the Hamming distance.The reverse 1-median problem is to reduce the overall sum of the weighted distances from the vertices to a given vertex by changing the parameters in a network such that it can satisfy a given budget,and the cost for changing the parameters is as small as possible. Under the hamming distance,it shows that this problem is NP-hard.By using dynamic programming method, this problem is solved in a general network by changing the weights of vertices.%主要讨论哈明距离下网络中的1-重心问题的反问题.1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值,使得给定的顶点到其他顶点的加权距离之和不超过一个给定的上界.证明了在哈明距离下该问题是NP困难的.并运用动态规划的思想,在考虑改变顶点的权的情况下,对一般网络进行了求解.