On Lovász--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP

DOI10.1137/040605849zbMath1122.90065OpenAlexW1977134485MaRDI QIDQ5470199

Kevin K. H. Cheung

Publication date: 30 May 2006

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

Full work available at URL: https://doi.org/10.1137/040605849

zbMATH Keywords

relaxationtraveling salesman problemintegrality gaplift-and-project

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (7)

On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications ⋮ The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem ⋮ Rank of Handelman hierarchy for Max-Cut ⋮ Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra ⋮ Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods

This page was built for publication: On Lovász--Schrijver Lift-and-Project Procedures on the Dantzig--Fulkerson--Johnson Relaxation of the TSP