A new approximation algorithm for the multilevel facility location problem

Adriana F. Gabor, Jan C.W. van Ommeren

Research output: Contribution to journalArticleAcademicpeer-review

29 Citations (Scopus)
56 Downloads (Pure)

Abstract

In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems.
Original languageEnglish
Pages (from-to)453-460
Number of pages8
JournalDiscrete applied mathematics
Volume158
Issue number5
DOIs
Publication statusPublished - 6 Mar 2010

Keywords

  • MSC-68W25
  • Approximation algorithms
  • Randomized algorithms
  • Facility location

Fingerprint Dive into the research topics of 'A new approximation algorithm for the multilevel facility location problem'. Together they form a unique fingerprint.

  • Cite this