Asymmetric Traveling Salesman Path and Directed Latency Problems

DOI10.1137/100797357zbMath1290.68058arXiv0907.0726OpenAlexW2062238337MaRDI QIDQ2862204

Zachary Friggstad, Zoya Svitkina, Mohammad R. Salavatipour

Publication date: 14 November 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0907.0726

zbMATH Keywords

approximation algorithmsintegrality gapdirected latency\(k\)-person traveling salesmen problemasymmetric traveling salesman path

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (4)

A constant-factor approximation for directed latency in quasi-polynomial time ⋮ A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time ⋮ The Chinese deliveryman problem ⋮ The asymmetric traveling salesman path LP has constant integrality ratio

This page was built for publication: Asymmetric Traveling Salesman Path and Directed Latency Problems