License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.329
URN: urn:nbn:de:0030-drops-51241
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5124/
Cohen-Addad, Vincent ;
Mathieu, Claire
Effectiveness of Local Search for Geometric Optimization
Abstract
What is the effectiveness of local search algorithms for geometric problems in the plane? We prove that local search with neighborhoods of magnitude 1/epsilon^c is an approximation scheme for the following problems in the Euclidean plane: TSP with random inputs, Steiner tree with random inputs, uniform facility location (with worst case inputs), and bicriteria k-median (also with worst case inputs). The randomness assumption is necessary for TSP.
BibTeX - Entry
@InProceedings{cohenaddad_et_al:LIPIcs:2015:5124,
author = {Vincent Cohen-Addad and Claire Mathieu},
title = {{Effectiveness of Local Search for Geometric Optimization}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {329--343},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-83-5},
ISSN = {1868-8969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5124},
URN = {urn:nbn:de:0030-drops-51241},
doi = {10.4230/LIPIcs.SOCG.2015.329},
annote = {Keywords: Local Search, PTAS, Facility Location, k-Median, TSP, Steiner Tree}
}
Keywords: |
|
Local Search, PTAS, Facility Location, k-Median, TSP, Steiner Tree |
Collection: |
|
31st International Symposium on Computational Geometry (SoCG 2015) |
Issue Date: |
|
2015 |
Date of publication: |
|
12.06.2015 |