Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems
From MaRDI portal
Publication:2392924
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
dynamic programming; approximation algorithm; directed graphs; ATSP; LP rounding; tour; \(k\)-Stroll; \(k\)-Tour; ATSPP; stroll
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