Rianne Veenstra — Smoothed Analysis of the 2-Opt Heuristic for the TSP
| Time: | Wednesday, July 3rd, 2013, 12:45-13:30 |
| Location: | Citadel, H327 |
One of the most basic heuristics for the famous Traveling Salesman Problem is the 2-Opt heuristic. The practical performance of this heuristic is pretty good, while the worst-case performance is exponential. We have looked at the TSP in the unit hypercube [0; 1]^d and performed a so called "smoothed analysis", in which an adversary specifies an instance in [0; 1]^d, which is then perturbed using a Gaussian distribution with variance sigma^2. By looking at the minimum improvement of pairs of 2-Opt steps we found upper bounds on the expected number of steps 2-Opt performs on this perturbed instance.