### Abstract

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

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

}

*Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization.*Özyegin Üniversitesi and Marmara Üniversitesi, Istanbul, Turkey, pp. 1-4, 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2015, Istanbul, Turkey, 26/05/15.

**Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP.** / Künnemann, Marvin; Manthey, Bodo.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Smoothed Approximation Ratio of the 2-Opt Heuristic for the TSP

AU - Künnemann, Marvin

AU - Manthey, Bodo

PY - 2015/5/26

Y1 - 2015/5/26

N2 - 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.

AB - 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.

KW - EWI-25941

KW - IR-96321

KW - METIS-312554

KW - Smoothed Analysis

KW - Traveling Salesman Problem

M3 - Conference contribution

SN - not assigned

SP - 1

EP - 4

BT - Proceedings of the 13th Cologne-Twente Workshop on Graphs and Combinatorial Optimization

A2 - Alkaya, A.F.

A2 - Duman, E.

PB - Özyegin Üniversitesi and Marmara Üniversitesi

CY - Istanbul, Turkey

ER -