N&O Lecture: Bodo Manthey (University of Twente)

Everyone is invited to attend the CWI Lecture from Bodo Manthey with the title: Smoothed Analysis of the 2-Opt Heuristic for the TSPAbstract:  The 2-opt heuristic is a very simple local search heuristic for the traveling salesman problem.
  • N&O Lecture: Bodo Manthey (University of Twente)
  • 2016-06-14T12:00:00+02:00
  • 2016-06-14T13:00:00+02:00
  • Everyone is invited to attend the CWI Lecture from Bodo Manthey with the title: Smoothed Analysis of the 2-Opt Heuristic for the TSPAbstract:  The 2-opt heuristic is a very simple local search heuristic for the traveling salesman problem.
  • What Networks & Optimization
  • When 14-06-2016 from 12:00 to 13:00 (Europe/Amsterdam / UTC200)
  • Where Room L016, ground floor CWI
  • Web Visit external website
  • Add event to calendar iCal

Everyone is invited to attend the CWI Lecture from Bodo Manthey with the title: Smoothed Analysis of the 2-Opt Heuristic for the TSP

Abstract:  

The 2-opt heuristic is a very simple local search heuristic for the
traveling salesman problem. While it usually converges quickly in
practice to a good solution, its worst-case running-time and
approximation ratio are poor.

In order to explain the practical performance of 2-opt, we use smoothed
analysis: an adversary places n points arbitrarily, and then the points
are perturbed by adding independent Gaussian random variables of
standard deviation sigma. We show that the maximum expected running-time
that the adversary can achieve is bounded by a polynomial in n and
1/sigma and that the maximum expected approximation ratio is
O(log(1/sigma)).

(Joint work with Rianne Veenstra and Marvin Künnemann.)