Approximating Minimum-Cost Connected T-Joins

DOI10.1007/978-3-642-32512-0_10zbMath1322.68263OpenAlexW2950683345MaRDI QIDQ3167389

Zachary Friggstad, Zhihan Gao, Joseph Cheriyan

Publication date: 2 November 2012

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-642-32512-0_10

zbMATH Keywords

primal-dual methodtraveling salesman problemapproximation algorithmsLP rounding\(T\)-joinsprize-collecting problems\(s\)-\(t\)-path TSP

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (3)

An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem

This page was built for publication: Approximating Minimum-Cost Connected T-Joins