Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
From MaRDI portal
Publication:3603459
DOI10.1007/978-3-540-74208-1_8zbMath1171.90507OpenAlexW2137717103MaRDI QIDQ3603459
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
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
