|Table of Contents|

[1] Yang Liping, Guan Xiucui,. 2-median location improvement problemsunder weighted l1 norm and l∞ norm on trees [J]. Journal of Southeast University (English Edition), 2013, 29 (3): 346-351. [doi:10.3969/j.issn.1003-7985.2013.03.021]
Copy

2-median location improvement problemsunder weighted l1 norm and l∞ norm on trees()
在赋权l1模和l∞模下树上的2-重心选址改进问题
Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:
29
Issue:
2013 3
Page:
346-351
Research Field:
Mathematics, Physics, Mechanics
Publishing date:
2013-09-20

Info

Title:
2-median location improvement problemsunder weighted l1 norm and l∞ norm on trees
在赋权l1模和l∞模下树上的2-重心选址改进问题
Author(s):
Yang Liping, Guan Xiucui
Department of Mathematics, Southeast University, Nanjing 211189, China
杨利平, 关秀翠
东南大学数学系, 南京 211189
Keywords:
2-median;  network improvement problem;  tree;  knapsack problem;  l1 norm;  l∞ norm
2-重心;  网络改进问题;  树;  背包问题;  l1模;  l∞模
PACS:
O224
DOI:
10.3969/j.issn.1003-7985.2013.03.021
Abstract:
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是树上顶点的个数.

References:

[1] Burkard R E, Pleschiutschnig C, Zhang J Z. Inverse median problems [J]. Discrete Optimization, 2004, 1(1): 23-39.
[2] Guan X C, Zhang B W. Inverse 1-median problem on trees under weighted l∞ norm [C]//Lecture Notes in Computer Science. Springer, 2010, 6124: 150-160.
[3] Guan X C, Zhang B W. Inverse 1-median problem on trees under weighted Hamming distance [J]. Journal of Global Optimization, 2012, 54(1): 75-82.
[4] Berman O. Improving the location of minsum facilities through network modification [J]. Annals of Operations Research, 1992, 40(1): 1-16.
[5] Burkard R E, Gassner E, Hatzl J. Reverse 2-median problem on trees [J]. Discrete Applied Mathematics, 2008, 156(11): 1963-1976.
[6] Bai Y Q, Wang Q, Wu L S. Reverse 1-median problem under Hamming distance [J]. Computer Engineering and Applications, 2011, 47(19): 39-41.(in Chinese)
[7] Bai Y Q, Wang Q, Wu L S. Reverse 1-median problem on a cycle under Hamming distance [J]. Mathematics in Practice and Theory, 2011, 41(17): 113-118.(in Chinese)
[8] Silvano M, Paolo T. Knapsack problems: algorithms and computer implementations [M]. New York: John Wiley and Sons Ltd., 1990: 13-18.
[9] Balas E, Zemel E. An algorthim for large zero-one knapsack problems [J]. Operations Research, 1980, 28(5): 1130-1154.

Memo

Memo:
Biographies: Yang Liping(1987—), female, graduate; Guan Xiucui(corresponding author), female, associate professor, xcguan@163.com.
Foundation item: The National Natural Science Foundation of China(No.10801031).
Citation: Yang Liping, Guan Xiucui. 2-median location improvement problems under weighted l1 norm and l∞ norm on trees[J].Journal of Southeast University(English Edition), 2013, 29(3):346-351.[doi:10.3969/j.issn.1003-7985.2013.03.021]
Last Update: 2013-09-20