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