文章基本信息

标题：Effectiveness of Local Search for Geometric Optimization
本地全文：下载
作者：Vincent Cohen-Addad ; Claire Mathieu
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：34
页码：329-343
DOI：10.4230/LIPIcs.SOCG.2015.329
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Local Search; PTAS; Facility Location; k-Median; TSP; Steiner Tree