Improved algorithms for joint optimization of facility locations and network connections

Xiaofan Lai, Zhou Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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 languageEnglish
Pages (from-to)745-753
Number of pages9
JournalEuropean Journal of Operational Research
Volume250
Issue number3
DOIs
Publication statusPublished - 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

Cite this