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

DOI10.1137/040605849MaRDI QIDQ5470199zbMATH OpenOpenAlexFDO

Authors 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

integrality gaplift-and-projectrelaxationtraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6347354
• Lift and project relaxations for the matching and related polytopes
• Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure
• A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem
• Rank bounds for a hierarchy of Lovász and Schrijver

Cited in

(7)

• Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications
• Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
• A comprehensive analysis of polyhedral lift-and-project methods
• Complexity analyses of Bienstock-Zuckerberg and lasserre relaxations on the matching and stable set polytopes
• On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy
• Rank of Handelman hierarchy for Max-Cut
• The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470199)