An Efficient Algorithm for Reverse 2-median Problem on A Cycle
|
| Title | An Efficient Algorithm for Reverse 2-median Problem on A Cycle |
| Authors | |
| Abstract | Location problems exist extensively in the real world and they mainly deal with finding optimal locations for facilities. However, the reverse location problem is also often met in practice, in which the facilities may already exist in a network and cannot be moved to a new place, the task is to improve the network within a given budget such that the improved network works as efficient as possible. This paper is dedicated to the problem of how to use a limited budget to modify the lengths of the edges on a cycle such that the overall sum of the weighted distances of the vertices to the respective closest facility of two prespecified vertices becomes as small as possible (shortly, R2MC problem). It has already been shown that the reverse 2-median problem with edge length modification on general graphs is strongly NP-hard. In this paper, we transform the R2MC problem to a reverse 3-median problem on a path and show that this problem can be solved efficiently by strongly polynomial algorithm. |
| Publisher | ACADEMY PUBLISHER |
| Date | 2010-10-01 |
| Source | Journal of Networks Vol 5, No 10 (2010): Special Issue: Information Security and Applications |
| Rights | Copyright © ACADEMY PUBLISHER - All Rights Reserved.To request permission, please check out URL: http://www.academypublisher.com/copyrightpermission.html. |