Replica Placement on Bounded Treewidth Graphs
| Autor: | Aggarwal, Anshul, Chakaravarthy, Venkatesan T., Gupta, Neelima, Sabharwal, Yogish, Sharma, Sachin, Thakral, Sonika |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We consider the replica placement problem: given a graph with clients and nodes, place replicas on a minimum set of nodes to serve all the clients; each client is associated with a request and maximum distance that it can travel to get served and 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 covering. It admits an O(\log n)-approximation and it is NP-hard to approximate within a factor of $o(\log n)$. We study the problem in terms of the treewidth $t$ of the graph and present an O(t)-approximation algorithm. Comment: An abridged version of this paper is to appear in the proceedings of WADS'17 |
| Databáze: | arXiv |
| Externí odkaz: |
|