Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/22649
Title: Multi-facility ordered median problems in directed networks
Authors: Tang, H
Cheng, TCE 
Ng, CT 
Keywords: Algorithms
finite dominating sets
multi-facility ordered median problem
pseudo-equilibria
Issue Date: 2011
Source: Journal of systems science and complexity, 2011, v. 24, no. 1, p. 61-67 How to cite?
Journal: Journal of Systems Science and Complexity 
Abstract: This paper uses a finite dominating set (FDS) to investigate the multi-facility ordered median problem (OMP) in a strongly connected directed network. The authors first prove that the multi-facility OMP has an FDS in the node set, which not only generalizes the FDS result provided by Kalcsics, et al. (2002), but also extends the FDS result from the single-facility case to the multiple case, filling an important gap. Then, based on this FDS result, the authors develop an exact algorithm to solve the problem. However, if the number of facilities is large, it is not practical to find the optimal solution, because the multi-facility OMP in directed networks is NP-hard. Hence, we present a constant-approximation algorithm for the p-median problem in directed networks. Finally, we pose an open problem for future research.
URI: http://hdl.handle.net/10397/22649
ISSN: 1009-6124
DOI: 10.1007/s11424-011-9327-2
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

2
Last Week
0
Last month
0
Citations as of Aug 17, 2017

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
0
Citations as of Aug 21, 2017

Page view(s)

60
Last Week
1
Last month
Checked on Aug 21, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.