Polynomial-Time Separation of a Superclass of Simple Comb Inequalities

DOI10.1287/MOOR.1060.0214MaRDI QIDQ5388004zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Lisa Fleischer, Adam N. Letchford, Andrea Lodi

Publication date 27 May 2008

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/589ac0056e43e6efdc551285091c2dcba339f536

zbMATH Keywords

cutting planesseparationtraveling salesman problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 2086916
• Separating a superclass of comb inequalities in planar graphs
• On the complexity of polyhedral separability
• scientific article; zbMATH DE number 4047102
• The complexity of cover inequality separation
• A class of linear complementarity problems solvable in polynomial time
• Polynomial-time computable approximation of families of semialgebraic sets and combinatorial complexity
• Complexity of a class of nonlinear combinatorial problems related to their linear counterparts
• Combinatorial optimization problems related to the committee polyhedral separability of finite sets
• scientific article; zbMATH DE number 5598224

Cited in

(8)

• Efficient separation routines for the symmetric traveling salesman problem. II: Separating multi handle inequalities.
• A note on the polytope of bipartite TSP
• Facets from gadgets
• Separating maximally violated comb inequalities in planar graphs
• Separating a superclass of comb inequalities in planar graphs
• scientific article; zbMATH DE number 2086916 (Why is no real title available?)
• On the \({\mathcal {H}}\)-free extension complexity of the TSP
• Exploiting planarity in separation routines for the symmetric traveling salesman problem

This page was built for publication: Polynomial-Time Separation of a Superclass of Simple Comb Inequalities

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