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...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.展开更多
基金This research is supported by the National Natural Science Foundation of China under Grant No. 70901050 and Macao Foundation under Grant No. 0144.
文摘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.
