Separating maximally violated comb inequalities in planar graphs

DOI10.1007/3-540-61310-2_35MaRDI QIDQ4645943zbMATH OpenOpenAlexFDO

Authors Lisa Fleischer, Éva Tardos

Publication date 11 January 2019

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://hdl.handle.net/1813/9034

zbMATH Keywords

fractional solutionHamiltonian cycleplanar graphseparation algorithmtravel salesman problem

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Recommendations

• Separating maximally violated comb inequalities in planar graphs
• Efficient separation routines for the symmetric traveling salesman problem. II: Separating multi handle inequalities.
• Separating a superclass of comb inequalities in planar graphs
• scientific article; zbMATH DE number 1342122
• scientific article; zbMATH DE number 2086916

Cites work

• Augmenting undirected connectivity in RNC and in randomized \(\tilde{O}(n^3)\) time
• Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
• scientific article; zbMATH DE number 177555 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 1256719 (Why is no real title available?)
• scientific article; zbMATH DE number 742961 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• On the symmetric travelling salesman problem I: Inequalities
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• On the symmetric travelling salesman problem: Solution of a 120-city problem
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Separating clique tree and bipartition inequalities in polynomial time
• Separating maximally violated comb inequalities in planar graphs
• Solution of large-scale symmetric travelling salesman problems
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• The Traveling-Salesman Problem and Minimum Spanning Trees

Cited in

(10)

• Efficient separation routines for the symmetric traveling salesman problem. I: General tools and comb separation
• On the separation of maximally violated mod-\(k\) cuts
• Separating maximally violated comb inequalities in planar graphs
• Separating a superclass of comb inequalities in planar graphs
• Combinatorial algorithms in concorde
• scientific article; zbMATH DE number 1342122 (Why is no real title available?)
• scientific article; zbMATH DE number 2086916 (Why is no real title available?)
• Separating clique tree and bipartition inequalities in polynomial time
• Separation Algorithms for Classes of STSP Inequalities Arising from a New STSP Relaxation
• Facet identification for the symmetric traveling salesman polytope

This page was built for publication: Separating maximally violated comb inequalities in planar graphs

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