Abstract
This paper studies a k-median Steiner forest problem that jointly optimizes the opening of at most k facility locations and their connections to the client locations, so that each client is connected by a path to an open facility, with the total connection cost minimized. The problem has wide applications in the telecommunication and transportation industries, but is strongly NP-hard. In the literature, only a 2-approximation algorithm is known, it being based on a Lagrangian relaxation of the problem and using a sophisticated primal-dual schema. In this study, we have developed an improved approximation algorithm using a simple transformation from an optimal solution of a minimum spanning tree problem. Compared with the existing 2-approximation algorithm, our new algorithm not only achieves a better approximation ratio that is easier to be proved, but also guarantees to produce solutions of equal or better quality - up to 50 percent improvement in some cases. In addition, for two non-trivial special cases, where either every location contains a client, or all the locations are in a tree-shaped network, we have developed, for the first time in the literature, new algorithms that can solve the problem to optimality in polynomial time.
Original language | English |
---|---|
Pages (from-to) | 745-753 |
Number of pages | 9 |
Journal | European Journal of Operational Research |
Volume | 250 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1 May 2016 |
Keywords
- Approximation algorithm
- Facility location
- Network connection
- Polynomial time algorithm
- Steiner forest
ASJC Scopus subject areas
- Modelling and Simulation
- Management Science and Operations Research
- Information Systems and Management