Smoothed analysis of partitioning algorithms for Euclidean functionals

Markus Bläser, Bodo Manthey, B.V. Raghavendra Rao

Research output: Contribution to journalArticleAcademicpeer-review

11 Citations (Scopus)
56 Downloads (Pure)

Abstract

Euclidean optimization problems such as TSP and minimum-length matching admit fast partitioning algorithms that compute near-optimal solutions on typical instances. In order to explain this performance, 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.
Original languageUndefined
Pages (from-to)397-418
Number of pages22
JournalAlgorithmica
Volume66
Issue number2
DOIs
Publication statusPublished - 2013

Keywords

  • EWI-21718
  • Karp's partitioning scheme
  • Partitioning heuristics
  • Smoothed Analysis
  • METIS-296425
  • Euclidean functionals
  • Euclidean optimization
  • IR-84622
  • Approximation algorithms
  • Probabilistic Analysis

Cite this