Approximating Connected Facility Location Problems via Random Facility Sampling and Core Detouring
| dc.contributor.author | Eisenbrand, Friedrich | |
| dc.contributor.author | Grandoni, Fabrizio | |
| dc.contributor.author | Rothvoß, Thomas | |
| dc.contributor.author | Schäfer, Guido | |
| dc.date.accessioned | 2021-12-17T10:07:28Z | |
| dc.date.available | 2021-12-17T10:07:28Z | |
| dc.date.issued | 2007 | |
| dc.description.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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15618 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14391 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | approximation algorithms | en |
| dc.subject.other | network design problems | en |
| dc.subject.other | connected facility location | en |
| dc.subject.other | single-sink rent-or-buy | en |
| dc.title | Approximating Connected Facility Location Problems via Random Facility Sampling and Core Detouring | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2007, 26 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |