Worst-case comparison of valid inequalities for the TSP

Cited In (46)

On the worst case performance of TESSA
Approximating TSP walks in subcubic graphs
Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
Computing compatible tours for the symmetric traveling salesman problem
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
A fast $(2 + \frac{2}{7})$-approximation algorithm for capacitated cycle covering
A Fast $$(2 + 2/7)$$-Approximation Algorithm for Capacitated Cycle Covering
On the graphical relaxation of the symmetric traveling salesman polytope
The nonidealness index of rank-ideal matrices
Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
Improved integrality gap upper bounds for traveling salesperson problems with distances one and two
A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts
The strongest facets of the acyclic subgraph polytope are unknown
The indefinite period traveling salesman problem
Theoretical challenges towards cutting-plane selection
A $\frac{9}{7}$-approximation algorithm for graphic TSP in cubic bipartite graphs
On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances
A new integer programming formulation of the graphical traveling salesman problem
Spanning closed walks and TSP in 3-connected planar graphs
On the facial structure of symmetric and graphical traveling salesman polyhedra
Aggregation-based cutting-planes for packing and covering integer programs
On the relative strength of split, triangle and quadrilateral cuts
Properties of some ILP formulations of a class of partitioning problems
On the core of traveling salesman games
Approximating polyhedra with sparse inequalities
Title not available (Why is that?)
Lift-and-project ranks of the set covering polytope of circulant matrices
Relaxations of mixed integer sets from lattice-free polyhedra
Relaxations of mixed integer sets from lattice-free polyhedra
Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem
Title not available (Why is that?)
Shorter tours and longer detours: uniform covers and a bit beyond
The salesman's improved tours for fundamental classes
Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours
Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs
Computing in combinatorial optimization
Title not available (Why is that?)
TSP Tours in Cubic Graphs: Beyond 4/3
The traveling salesman problem on cubic and subcubic graphs
Easy and hard separation of sparse and dense odd-set constraints in matching
Strength of facets for the set covering and set packing polyhedra on circulant matrices
The worst case analysis of strong knapsack facets
A review on quantum approximate optimization algorithm and its variants
Integrality gap of the vertex cover linear programming relaxation

This page was built for publication: Worst-case comparison of valid inequalities for the TSP

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