A new approximation algorithm for the multilevel facility location problem

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

Research output: Book/ReportReportProfessional

323 Downloads (Pure)

Abstract

In this paper we propose a new integer programming formulation for the multi-level facility location problem and a novel 3-approximation algorithm based on LP rounding. The linear program we are using has a polynomial number of variables and constraints, being thus more efficient than the one commonly used in the approximation algorithms for this type of problems.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages15
Publication statusPublished - Dec 2007

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherUniversity of Twente, Department of Applied Mathematics
No.Supplement/1862
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Keywords

  • IR-64504
  • MSC-90B80
  • METIS-245827
  • MSC-68W25
  • MSC-68W20
  • EWI-11503
  • MSC-90C10

Cite this