Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14391
For citation please use:
Main Title: Approximating Connected Facility Location Problems via Random Facility Sampling and Core Detouring
Author(s): Eisenbrand, Friedrich
Grandoni, Fabrizio
Rothvoß, Thomas
Schäfer, Guido
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15618
http://dx.doi.org/10.14279/depositonce-14391
License: http://rightsstatements.org/vocab/InC/1.0/
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.
Subject(s): approximation algorithms
network design problems
connected facility location
single-sink rent-or-buy
Issue Date: 2007
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2007, 26
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-026-2007.pdf
Format: Adobe PDF | Size: 115.65 kB
DownloadShow Preview
Thumbnail
Report-026-2007.ps.gz
Format: Unknown | Size: 66.97 kB
Download

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.