The Inverse 1-Median Problem on Tree Networks with Variable Real Edge Lengths

Longshu Wu, Joonwhoan Lee, Jianhua Zhang and Qin Wang

Mathematical Problems in Engineering, 2013, vol. 2013, 1-6

Abstract:

Location problems exist in the real world and they mainly deal with finding optimal locations for facilities in a network, such as net servers, hospitals, and shopping centers. The inverse location problem is also often met in practice and has been intensively investigated in the literature. As a typical inverse location problem, the inverse 1-median problem on tree networks with variable real edge lengths is discussed in this paper, which is to modify the edge lengths at minimum total cost such that a given vertex becomes a 1-median of the tree network with respect to the new edge lengths. First, this problem is shown to be solvable in linear time with variable nonnegative edge lengths. For the case when negative edge lengths are allowable, the NP-hardness is proved under Hamming distance, and strongly polynomial time algorithms are presented under and norms, respectively.

Date: 2013
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2013/313868.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2013/313868.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:313868

DOI: 10.1155/2013/313868

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().