摘要
This paper focuses on the 2-median location improvement problem on tree networks and the problem is to modify the weights of edges at the minimum cost such that the overall sum of the weighted distance of the vertices to the respective closest one of two prescribed vertices in the modified network is upper bounded by a given value.l1 norm and l∞norm are used to measure the total modification cost. These two problems have a strong practical application background and important theoretical research value. It is shown that such problems can be transformed into a series of sum-type and bottleneck-type continuous knapsack problems respectively.Based on the property of the optimal solution two O n2 algorithms for solving the two problems are proposed where n is the number of vertices on the tree.
研究了在树网络上的2-重心选址改进问题,该问题是指以最少的花费调整各边的权值使得修改后网络中所有顶点到2个预设点的赋权距离的和不超过给定的上界.采用l1模和l∞模衡量总的修改花费.这2类问题具有较强的实际应用价值与理论研究价值.这2类改进问题可分别等价地转化为一系列的和型及瓶颈型的连续背包问题,基于最优解的特性,提出了时间复杂度为O(n2)的算法来求解这2类问题,其中n是树上顶点的个数.
基金
The National Natural Science Foundation of China(No.10801031)
