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.)
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.
Share this page
When
14 Jun 2016
from noon
to 14 Jun 2016 1 p.m.
CEST (GMT+0200)
Where
Room L016, ground floor CWI
Web
Add