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

Reverse 1-median problem under Hamming distance

作　　者：白艳琴[1] 王勤[1] 吴龙树[1] 

机构地区：[1]中国计量学院理学院数学系,杭州310018

出　　处：《计算机工程与应用》2011年第19期39-41,共3页Computer Engineering and Applications

基　　金：国家自然科学基金No.10601051;浙江省自然科学基金(No.Y6090472);浙江省教育厅科研项目(No.Y201018835)~~

摘　　要：主要讨论哈明距离下网络中的1-重心问题的反问题。1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值,使得给定的顶点到其他顶点的加权距离之和不超过一个给定的上界。证明了在哈明距离下该问题是NP困难的。并运用动态规划的思想,在考虑改变顶点的权的情况下,对一般网络进行了求解。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-重心 哈明距离 反问题 动态规划 NP困难 

分 类 号：O221[理学—运筹学与控制论] TP301[理学—数学]