Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems

DOI10.1007/s00453-011-9610-6zbMath1272.90064MaRDI QIDQ2392924

Julia Chuzhoy, MohammadHossein Bateni

Publication date: 5 August 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9610-6

zbMATH Keywords

dynamic programming; approximation algorithm; directed graphs; ATSP; LP rounding; tour; \(k\)-Stroll; \(k\)-Tour; ATSPP; stroll

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximation algorithms for deadline-TSP and vehicle routing with time-windows
• Polylogarithmic inapproximability
• Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
• Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems
• Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• A Reduction Method for Edge-Connectivity in Graphs
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees