网络1-重心反问题的计算复杂性研究

摘要

在网络中顶点的权值可以改变的情况下,对哈明距离下以及l1模下1-重心问题的反问题进行研究.通过将哈明距离下网络1-重心问题的反问题归约为0-1背包问题,证明即使是在链式网络中,在哈明距离下该问题仍是NP困难的,并给出l1模下在一般网络中求解1-重心反问题的多项式时间算法.%This paper researches the reverse 1-median problem under the hamming distance and l1-norm in condition that the weights of vertices in a network can be changed. Under the hamming distance, by transforming this problem to a 0-1 knapsack problem, it proves that even in chain network, this problem is NP-hard. Underl1-norm, it presents a polynomial time algorithm to solve the problem in general network.