scientific article

DOI10.4086/cjtcs.2014.001zbMath1366.90187arXiv1107.1265OpenAlexW4248639061MaRDI QIDQ3191144

No author found.

Publication date: 24 September 2014

Published in: Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

integrality gapslift-and-projecttraveling salesperson problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (1)

On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• The traveling salesman problem and its variations.
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Improved Inapproximability for TSP
• The Directed Minimum Latency Problem
• A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• Heuristic analysis, linear programming and branch and bound
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Improving christofides' algorithm for the s-t path TSP
• Approximating Graphic TSP by Matchings

This page was built for publication: