Abstract
We identify a finite dominating set (FDS) for a special case of the multi-facility ordered median problem in networks, in which the λ-weights can take at least two different values. This FDS result not only includes the FDS research for the p-center problem, but also extends the case of a < b in the λ-weights provided by Kalcsics et al. (Kalcsics, J., Nickel, S., Puerto, J. (2003). Multi-facility ordered median problems: A further analysis. Networks, 41(1), 1-12). Furthermore, based on the FDS result, we devise an exact algorithm for the problem. In addition, we present a polynomial time algorithm for the problem with at most three different values in the λ-weights in tree networks. Finally, we pose an open problem on identifying the existence of a polynomial size FDS for the multi-facility convex ordered median problem in networks.
Original language | English |
---|---|
Pages (from-to) | 707-712 |
Number of pages | 6 |
Journal | Computers and Industrial Engineering |
Volume | 57 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1 Oct 2009 |
Keywords
- Algorithms
- Finite dominating sets
- Multi-facility ordered median problem
- Pseudo-equilibria
ASJC Scopus subject areas
- General Computer Science
- General Engineering