Smoothed analysis of partitioning algorithms for Euclidean functionals

Bläser, Markus and Manthey, Bodo and Rao, B.V. Raghavendra (2011) Smoothed analysis of partitioning algorithms for Euclidean functionals. In: 12th International Symposium on Algorithms and Data Structures, WADS 2011, 15-17 Aug 2011, New York, NY, USA.

PDF
Restricted to UT campus only: Request a copy
334Kb

Abstract:	Euclidean optimization problems such as TSP and minimum-length matching admit fast partitioning algorithms that compute near-optimal solutions on typical instances. We develop a general framework for the application of smoothed analysis to partitioning algorithms for Euclidean optimization problems. Our framework can be used to analyze both the running-time and the approximation ratio of such algorithms. We apply our framework to obtain smoothed analyses of Dyer and Frieze's partitioning algorithm for Euclidean matching, Karp's partitioning scheme for the TSP, a heuristic for Steiner trees, and a heuristic for degree-bounded minimum-length spanning trees.
Item Type:	Conference or Workshop Item
Copyright:	© 2011 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/78129
Official URL:	http://dx.doi.org/10.1007/978-3-642-22300-6_10
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page