Paper Info
Title
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.
Year
Venue
Field
2015
Symposium on Computational Geometry
Discrete mathematics,Magnitude (mathematics),Combinatorics,Mathematical optimization,Computer science,Steiner tree problem,Geometric problems,Facility location problem,Euclidean geometry,Local search (optimization),Randomness
DocType
Citations 
PageRank 
Conference
8
0.51
References 
Authors
0
2
Name
Order
Citations
PageRank
Vincent Cohen-Addad18525.47
Claire Mathieu245225.78