Approximation algorithms for facility location problems with discrete subadditive cost functions

Research output: Book/ReportReportProfessional

13 Downloads (Pure)

Abstract

In this article we focus on approximation algorithms for facility location problems with subadditive costs. As examples of such problems, we present two facility location problems with stochastic demand and exponential servers, respectively inventory. We present a $(1+\epsilon,1)$- reduction of the facility location problem with subadditive costs to a soft capacitated facility location problem, which implies the existence of a $2(1+\epsilon)$ approximation algorithm. For a special subclass of subadditive functions, we obtain a 2-approximation algorithm by reduction to the linear cost facility location problem.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
ISBN (Print)0169-2690
Publication statusPublished - 2005

Publication series

Namememorandum
PublisherUniversity of Twente, Department of Applied Mathematics
No.1779
ISSN (Print)0169-2690

Keywords

  • MSC-68W25
  • MSC-90B06
  • METIS-224473
  • IR-65963
  • EWI-3599
  • MSC-60K30

Cite this

Gabor, A. F., & van Ommeren, J. C. W. (2005). Approximation algorithms for facility location problems with discrete subadditive cost functions. (memorandum; No. 1779). Enschede: University of Twente, Department of Applied Mathematics.