### Abstract

The 2-Opt heuristic is a simple, easy-to-implement local search heuristic for the traveling salesman problem. While it usually provides good approximations to the optimal tour in experiments, its worst-case performance is poor. In an attempt to explain the approximation performance of 2-Opt, we prove an upper bound of exp(O(sqrt(log(1/sigma))) for the smoothed approximation ratio of 2-Opt. As a lower bound, we prove that the worst-case lower bound of Omega(log n/log log n) for the approximation ratio holds for sigma = O(1/ sqrt(n)).
Our main technical novelty is that, different from existing smoothed analyses, we do not separately analyze objective values of the global and the local optimum on all inputs, but simultaneously bound them on the same input.

Original language | Undefined |
---|---|

Title of host publication | Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization |

Editors | A.F. Alkaya, E. Duman |

Place of Publication | Istanbul, Turkey |

Publisher | Özyegin Üniversitesi and Marmara Üniversitesi |

Pages | 1-4 |

Number of pages | 4 |

ISBN (Print) | not assigned |

Publication status | Published - 26 May 2015 |

Event | 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2015 - Marmara University , Istanbul, Turkey Duration: 26 May 2015 → 28 May 2015 Conference number: 13 http://ctw2015.eng.marmara.edu.tr/ |

### Publication series

Name | |
---|---|

Publisher | Özyegin Üniversitesi and Marmara Üniversitesi |

### Workshop

Workshop | 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2015 |
---|---|

Abbreviated title | CTW |

Country | Turkey |

City | Istanbul |

Period | 26/05/15 → 28/05/15 |

Internet address |

### Keywords

- EWI-25941
- IR-96321
- METIS-312554
- Smoothed Analysis
- Traveling Salesman Problem

## Cite this

Künnemann, M., & Manthey, B. (2015). Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP. In A. F. Alkaya, & E. Duman (Eds.),

*Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization*(pp. 1-4). Istanbul, Turkey: Özyegin Üniversitesi and Marmara Üniversitesi.