Approximation Algorithms for Traveling Salesman Problems / Vera Traub and Jens Vygen.

Format:

Book

Author/Creator:

Traub, Vera, author.

Vygen, Jens, author.

Language:

English

Subjects (All):

Traveling salesman problem.

Approximation algorithms.

Physical Description:

1 online resource (xiv, 427 pages) : digital, PDF file(s).

Edition:

First edition.

Place of Publication:

Cambridge, England : Cambridge University Press, [2025]

Summary:

"This is the first book on approximation algorithms for the Traveling Salesman Problem, a central topic in discrete mathematics, theoretical computer science, and combinatorial optimization. It presents the state of the art comprehensively as well as advances it, making it an excellent resource for teaching, selfstudy, and further research"-- Provided by publisher

Contents:

Linear programming relaxations of the symmetric TSP

Linear programming relaxations of the asymmetric TSP

Duality, cuts, and uncrossing

Thin trees and random trees

Asymmetric graph TSP

Constant-factor approximation for the asymmetric TSP

Algorithms for subtour cover

Asymmetric path TSP

Parity correction of random trees

Proving the main payment theorem for hierarchies

Removable pairings

Ear-decompositions, matchings, and matroids

Symmetric path TSP and T-tours

Best-of-many Christofides and variants

Path TSP by dynamic programming

Further results, related problems

State of the art, open problems

Notes:

Title from publisher's bibliographic system (viewed on 15 Nov 2024).

Description based on print version record.

Includes bibliographical references and index.

ISBN:

9781009445429

1009445421

9781009445436

100944543X