|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()
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
Author(s):
Yang Liping;  Guan Xiucui
Department of Mathematics, Southeast University, Nanjing 211189, China
Keywords:
2-median;  network improvement problem;  tree;  knapsack problem;  l1 norm;  l∞ norm
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.

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