Book contents
- Frontmatter
- Preface
- Contents
- 1 Introduction
- 2 Linear Programming Relaxations of the Symmetric TSP
- 3 Linear Programming Relaxations of the Asymmetric TSP
- 4 Duality, Cuts, and Uncrossing
- 5 Thin Trees and Random Trees
- 6 Asymmetric Graph TSP
- 7 Constant-Factor Approximation for the Asymmetric TSP
- 8 Algorithms for Subtour Cover
- 9 Asymmetric Path TSP
- 10 Parity Correction of Random Trees
- 11 Proving the Main Payment Theorem for Hierarchies
- 12 Removable Pairings
- 13 Ear-Decompositions, Matchings, and Matroids
- 14 Symmetric Path TSP and T-Tours
- 15 Best-of-Many Christofides and Variants
- 16 Path TSP by Dynamic Programming
- 17 Further Results, Related Problems
- 18 State of the Art, Open Problems
- Bibliography
- Index
1 - Introduction
Published online by Cambridge University Press: 14 November 2024
Book contents
- Frontmatter
- Preface
- Contents
- 1 Introduction
- 2 Linear Programming Relaxations of the Symmetric TSP
- 3 Linear Programming Relaxations of the Asymmetric TSP
- 4 Duality, Cuts, and Uncrossing
- 5 Thin Trees and Random Trees
- 6 Asymmetric Graph TSP
- 7 Constant-Factor Approximation for the Asymmetric TSP
- 8 Algorithms for Subtour Cover
- 9 Asymmetric Path TSP
- 10 Parity Correction of Random Trees
- 11 Proving the Main Payment Theorem for Hierarchies
- 12 Removable Pairings
- 13 Ear-Decompositions, Matchings, and Matroids
- 14 Symmetric Path TSP and T-Tours
- 15 Best-of-Many Christofides and Variants
- 16 Path TSP by Dynamic Programming
- 17 Further Results, Related Problems
- 18 State of the Art, Open Problems
- Bibliography
- Index
HTML view is not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
Summary
In this introductory chapter, we will formally introduce the main variants of the traveling salesman problem, symmetric and asymmetric, explain a very useful graph-theoretic view based on Euler’s theorem, and describe the classical simple approximation algorithms: Christofides’ algorithm and the cycle cover algorithm.
We also introduce basic notation, in particular from graph theory, and some fundamental combinatorial optimization problems.
- Type
- Chapter
- Information
- Publisher: Cambridge University PressPrint publication year: 2024
You have
Access