Worst-case comparison of valid inequalities for the TSP
From MaRDI portal
(Redirected from Publication:1908019)
Recommendations
- Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
- The Binested Inequalities for the Symmetric Traveling Salesman Polytope
- scientific article; zbMATH DE number 3943560
- A new class of cutting planes for the symmetric travelling salesman problem
- The Crown Inequalities for the Symmetric Traveling Salesman Polytope
Cited in
(48)- 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
- On polynomial kernels for traveling salesperson problem and its generalizations
- Computing compatible tours for the symmetric traveling salesman problem
- A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering
- A proof of the Boyd-Carr conjecture
- On the graphical relaxation of the symmetric traveling salesman polytope
- The nonidealness index of rank-ideal matrices
- A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts
- 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
- The indefinite period traveling salesman problem
- A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs
- Theoretical challenges towards cutting-plane selection
- The strongest facets of the acyclic subgraph polytope are unknown
- A \(\frac{4}{3} \)-approximation algorithm for half-integral cycle cut instances of the TSP
- 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
- On the relative strength of split, triangle and quadrilateral cuts
- Aggregation-based cutting-planes for packing and covering integer programs
- Properties of some ILP formulations of a class of partitioning problems
- On the core of traveling salesman games
- TSP tours in cubic graphs: beyond 4/3
- Approximating polyhedra with sparse inequalities
- Semidefinite programming relaxations of the traveling salesman problem and their integrality gaps
- A fast (2 + 2/7)-approximation algorithm for capacitated cycle covering
- Lift-and-project ranks of the set covering polytope of circulant matrices
- Spanning closed walks and TSP in 3-connected planar graphs
- 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
- scientific article; zbMATH DE number 4199979 (Why is no real title available?)
- 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
- 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)
