Approximating connected facility location problems via random facility sampling and core detouring Export

@inproceedings{citeulike:5243203, abstract = {We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the facilities serving sampled clients in the approximate solution. Via a novel analytical tool, which we term core detouring , we show that this approach significantly improves over the previously best known approximation ratios for several NP-hard network design problems. For example, we reduce the approximation ratio for the connected facility location problem from 8.55 to 4.00 and for the single-sink rent-or-buy problem from 3.55 to 2.92. We show that our connected facility location algorithms can be derandomized at the expense of a slightly worse approximation ratio. The versatility of our framework is demonstrated by devising improved approximation algorithms also for other related problems.}, address = {Philadelphia, PA, USA}, author = {Eisenbrand, Friedrich and Grandoni, Fabrizio and Rothvoss, Thomas and Sch\"{a}fer, Guido}, booktitle = {SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms}, citeulike-article-id = {5243203}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1347082.1347210}, keywords = {network\_design, rent\_or\_buy}, location = {San Francisco, California}, pages = {1174--1183}, posted-at = {2009-07-23 22:45:22}, priority = {2}, publisher = {Society for Industrial and Applied Mathematics}, title = {Approximating connected facility location problems via random facility sampling and core detouring}, url = {http://portal.acm.org/citation.cfm?id=1347082.1347210}, year = {2008} }

TY - CONF ID - citeulike:5243203 L3 - citeulike-article-id:5243203 N2 - We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the facilities serving sampled clients in the approximate solution. Via a novel analytical tool, which we term core detouring , we show that this approach significantly improves over the previously best known approximation ratios for several NP-hard network design problems. For example, we reduce the approximation ratio for the connected facility location problem from 8.55 to 4.00 and for the single-sink rent-or-buy problem from 3.55 to 2.92. We show that our connected facility location algorithms can be derandomized at the expense of a slightly worse approximation ratio. The versatility of our framework is demonstrated by devising improved approximation algorithms also for other related problems. CY - San Francisco, California AD - Philadelphia, PA, USA EP - 1183 TI - Approximating connected facility location problems via random facility sampling and core detouring PB - Society for Industrial and Applied Mathematics T2 - SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms SP - 1174 KW - network_design KW - rent_or_buy AU - Eisenbrand, Friedrich AU - Grandoni, Fabrizio AU - Rothvoss, Thomas AU - Schäfer, Guido PY - 2008/// UR - http://portal.acm.org/citation.cfm?id=1347082.1347210 ER -