Connected facility location via random facility sampling and core detouring |
| |
Authors: | Friedrich Eisenbrand Fabrizio Grandoni Thomas Rothvoß Guido Schäfer |
| |
Affiliation: | 1. Institute of Mathematics, École Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland;2. Dipartimento di Informatica, Sistemi e Produzione, Università di Roma Tor Vergata, Via del Politecnico 1, 00133 Roma, Italy;3. Centrum Wiskunde & Informatica, PO Box 94079, 1090 GB Amsterdam, The Netherlands |
| |
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. 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|