TY - JOUR

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

AU - Gabor, Adriana F.

AU - van Ommeren, Jan Kees C.W.

PY - 2006/10/31

Y1 - 2006/10/31

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Inventory models

KW - Multi server queues

KW - Stochastic facility location

KW - Subadditive functions

UR - http://www.scopus.com/inward/record.url?scp=33749430509&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2006.04.013

DO - 10.1016/j.tcs.2006.04.013

M3 - Article

AN - SCOPUS:33749430509

SN - 0304-3975

VL - 363

SP - 289

EP - 300

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

ER -