Smoothed analysis of partitioning algorithms for Euclidean functionals

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)

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.
Original languageUndefined
Title of host publication12th International Symposium on Algorithms and Data Structures, WADS 2011
EditorsF. Dehne, J. Iacono, J.-R. Sack
Place of PublicationBerlin
PublisherSpringer
Pages110-121
Number of pages12
ISBN (Print)978-3-642-22299-3
DOIs
Publication statusPublished - 2011
Event12th International Symposium on Algorithms and Data Structures, WADS 2011 - New York, NY, USA
Duration: 15 Aug 201117 Aug 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume6844
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Symposium on Algorithms and Data Structures, WADS 2011
Period15/08/1117/08/11
Other15-17 Aug 2011

Keywords

  • METIS-278811
  • EWI-20544
  • IR-78129

Cite this