Approximation algorithms for facility location problems with a special class of subadditive cost functions

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

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

In this article we focus on approximation algorithms for facility location problems with subadditive costs. As examples of such problems, we present three facility location problems with stochastic demand and exponential servers, respectively inventory. We present a (1 + ε{lunate}, 1)-reduction of the facility location problem with subadditive costs to the soft capacitated facility location problem, which implies the existence of a 2 (1 + ε{lunate})-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 languageBritish English
Pages (from-to)289-300
Number of pages12
JournalTheoretical Computer Science
Volume363
Issue number3
DOIs
StatePublished - 31 Oct 2006

Keywords

  • Approximation algorithms
  • Inventory models
  • Multi server queues
  • Stochastic facility location
  • Subadditive functions

Fingerprint

Dive into the research topics of 'Approximation algorithms for facility location problems with a special class of subadditive cost functions'. Together they form a unique fingerprint.

Cite this