Reducing Path TSP to TSP (Q5860476)

From MaRDI portal

Jump to:navigation, search

scientific article; zbMATH DE number 7430748

Language	Label	Description	Also known as
English	Reducing Path TSP to TSP	scientific article; zbMATH DE number 7430748

Statements

scholarly article

0 references

Reducing Path TSP to TSP (English)

0 references

0 references

0 references

0 references

SIAM Journal on Computing

0 references

publication date

19 November 2021

0 references

zbMATH Keywords

traveling salesman problem

0 references

path TSP

0 references

approximation algorithm

0 references

MaRDI profile type

MaRDI publication profile

0 references

Improving Christofides' Algorithm for the s-t Path TSP

0 references

Approximation Algorithms for Orienteering and Discounted-Reward TSP

0 references

Approximating minimum-cost connected \(T\)-joins

0 references

Integer Programming and Algorithmic Geometry of Numbers

0 references

Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs

0 references

An application of simultaneous diophantine approximation in combinatorial optimization

0 references

An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem

0 references

0 references

Better \(s-t\)-tours by Gao trees

0 references

Geometric algorithms and combinatorial optimization.

0 references

Analysis of Christofides' heuristic: some paths are more difficult than cycles

0 references

A factor 2 approximation algorithm for the generalized Steiner network problem

0 references

An improved approximation algorithm for TSP in the half integral case

0 references

New inapproximability bounds for TSP

0 references

How to tidy up a symmetric set-system by use of uncrossing operations

0 references

Combinatorial optimization. Theory and algorithms

0 references

Removing and Adding Edges for the Traveling Salesman Problem

0 references

\(\frac{13}{9}\)-approximation for graphic TSP

0 references

A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond

0 references

A Randomized Rounding Approach to the Traveling Salesman Problem

0 references

The Traveling Salesman Problem with Distances One and Two

0 references

Combinatorial optimization. Polyhedra and efficiency (3 volumes)

0 references

Potentials in Undirected Graphs and Planar Multiflows

0 references

Eight-Fifth Approximation for the Path TSP

0 references

The Salesman’s Improved Paths through Forests

0 references

Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs

0 references

0 references

Improving on best-of-many-Christofides for \(T\)-tours

0 references

An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP

0 references

Approaching 3/2 for the <i>s</i> - <i>t</i> -path TSP

0 references

Reassembling Trees for the Traveling Salesman

0 references

A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots

0 references

A 1.5-Approximation for Path TSP

0 references

full work available at URL

https://doi.org/10.1137/20m135594x

0 references

Identifiers

10.1137/20M135594X

0 references

Mathematics Subject Classification ID

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5860476

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q5860476&oldid=37128122"