On the \({\mathcal {H}}\)-free extension complexity of the TSP

DOI10.1007/s11590-016-1029-1zbMath1368.90136arXiv1506.08311OpenAlexW2277265469MaRDI QIDQ519756

Hans Raj Tiwary, David Avis

Publication date: 5 April 2017

Published in: Optimization Letters (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsextended formulationscomb inequalitiestraveling salesman polytope

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Cites Work

• Extended formulations, nonnegative factorizations, and randomized communication protocols
• On the extension complexity of combinatorial polytopes
• A generalization of extension complexity that captures P
• A note on the extension complexity of the knapsack polytope
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• Odd Minimum Cut-Sets and b-Matchings
• The Matching Polytope has Exponential Extension Complexity
• Polynomial-Time Separation of a Superclass of Simple Comb Inequalities
• Linear vs. semidefinite extended formulations
• Extended formulations in combinatorial optimization

This page was built for publication: On the \({\mathcal {H}}\)-free extension complexity of the TSP