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

Reverse 1-median Problem on a Cycle under the Hamming Distance

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

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

出　　处：《数学的实践与认识》2011年第13期113-118,共6页Mathematics in Practice and Theory

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

摘　　要：主要讨论哈明距离下圈图上1-重心问题的反问题.1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值,使得给定的顶点到其它顶点的加权距离之和不超过一个给定的上界.通过将该问题转化为0-1背包问题,证明了在哈明距离下该问题是NP困难的,并运用动态规划的思想,在考虑改变边的长度的情况下,对圈图进行了求解.In this paper, we mainly consider the reverse 1-median problem on a cycle 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, by transforming this problem to a 0-1 knapsack problem, we show that this problem is NP-hard. By using dynamic programming method, we solve this problem on a cycle by changing the lengths of edges.

关 键 词：1-重心 哈明距离 反问题 动态规划 NP困难 

分 类 号：O224[理学—运筹学与控制论]