@InProceedings{10.1007/978-3-319-62127-2_2,
author="Aggarwal, Anshul
and Chakaravarthy, Venkatesan T.
and Gupta, Neelima
and Sabharwal, Yogish
and Sharma, Sachin
and Thakral, Sonika",
editor="Ellen, Faith
and Kolokolova, Antonina
and Sack, J{\"o}rg-R{\"u}diger",
title="Replica Placement on Bounded Treewidth Graphs",
booktitle="Algorithms and Data Structures",
year="2017",
publisher="Springer International Publishing",
address="Cham",
pages="13--24",
abstract="We consider the replica placement problem: given a graph and a set of clients, place replicas on a minimum set of nodes of the graph to serve all the clients; each client is associated with a request and maximum distance that it can travel to get served; there is a maximum limit (capacity) on the amount of request a replica can serve. The problem falls under the general framework of capacitated set cover. It admits an                                                                           {\$}{\$}O({\backslash}log n){\$}{\$}                -approximation and it is NP-hard to approximate within a factor of                                                                           {\$}{\$}o({\backslash}log n){\$}{\$}                . We study the problem in terms of the treewidth t of the graph and present an O(t)-approximation algorithm.",
isbn="978-3-319-62127-2"
}