Approximating Connected Facility Location Problems via Random Facility Sampling and Core Detouring

dc.contributor.authorEisenbrand, Friedrich
dc.contributor.authorGrandoni, Fabrizio
dc.contributor.authorRothvoß, Thomas
dc.contributor.authorSchäfer, Guido
dc.date.accessioned2021-12-17T10:07:28Z
dc.date.available2021-12-17T10:07:28Z
dc.date.issued2007
dc.description.abstractWe 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.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15618
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14391
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherapproximation algorithmsen
dc.subject.othernetwork design problemsen
dc.subject.otherconnected facility locationen
dc.subject.othersingle-sink rent-or-buyen
dc.titleApproximating Connected Facility Location Problems via Random Facility Sampling and Core Detouringen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften>Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2007, 26en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
Files
Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-026-2007.pdf
Size:
115.65 KB
Format:
Adobe Portable Document Format
Description:
Loading…
Thumbnail Image
Name:
Report-026-2007.ps.gz
Size:
66.97 KB
Format:
Unknown data format
Description:
Collections