在赋权l_1模和l_∞模下树上的2-重心选址改进问题(英文)

研究了在树网络上的2-重心选址改进问题,该问题是指以最少的花费调整各边的权值使得修改后网络中所有顶点到2个预设点的赋权距离的和不超过给定的上界.采用l1模和l∞模衡量总的修改花费.这2类问题具有较强的实际应用价值与理论研究价值.这2类改进问题可分别等价地转化为一系列的和型及瓶颈型的连续背包问题,基于最优解的特性,提出了时间复杂度为O(n2)的算法来求解这2类问题,其中n是树上顶点的个数.