000172412 001__ 172412
000172412 005__ 20181203022557.0
000172412 0247_ $$2doi$$a10.1016/j.jcss.2010.02.001
000172412 02470 $$2ISI$$a000281501900002
000172412 037__ $$aARTICLE
000172412 245__ $$aConnected facility location via random facility sampling and core detouring
000172412 269__ $$a2010
000172412 260__ $$c2010
000172412 336__ $$aJournal Articles
000172412 520__ $$aWe 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. The mentioned results 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. (C) 2010 Elsevier Inc. All rights reserved.
000172412 6531_ $$aConnected facility location
000172412 6531_ $$aApproximation algorithm
000172412 6531_ $$aRandomized algorithm
000172412 6531_ $$aNetwork design
000172412 6531_ $$aApproximation Algorithms
000172412 6531_ $$aNetwork Design
000172412 6531_ $$aSteiner Problem
000172412 6531_ $$aSimpler
000172412 700__ $$0240331$$g183121$$aEisenbrand, Friedrich
000172412 700__ $$aGrandoni, Fabrizio
000172412 700__ $$g183730$$aRothvoss, Thomas$$0243826
000172412 700__ $$aSchafer, Guido
000172412 773__ $$j76$$tJournal Of Computer And System Sciences$$q709-726
000172412 909C0 $$xU11879$$0252111$$pDISOPT
000172412 909CO $$pSB$$particle$$ooai:infoscience.tind.io:172412
000172412 917Z8 $$x183121
000172412 937__ $$aEPFL-ARTICLE-172412
000172412 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000172412 980__ $$aARTICLE