Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs

DOI10.1007/978-3-540-74208-1_8zbMath1171.90507OpenAlexW2137717103MaRDI QIDQ3603459

Mohit Singh, Uriel Feige

Publication date: 17 February 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74208-1_8

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (16)

Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ A survey on combinatorial optimization in dynamic environments ⋮ Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ The Directed Minimum Latency Problem ⋮ Deterministic Algorithms for Multi-criteria TSP ⋮ From symmetry to asymmetry: generalizing TSP approximations by parametrization ⋮ Deterministic algorithms for multi-criteria max-TSP ⋮ Approximation of the double traveling salesman problem with multiple stacks ⋮ The asymmetric traveling salesman path LP has constant integrality ratio ⋮ Reducing Path TSP to TSP ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem

This page was built for publication: Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs