Journal
THEORETICAL COMPUTER SCIENCE
Volume 363, Issue 3, Pages 289-300Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2006.04.013
Keywords
approximation algorithms; subadditive functions; stochastic facility location; multi server queues; inventory models
Categories
Ask authors/readers for more resources
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 + epsilon, 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 + 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. (C) 2006 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available