Worst-case comparison of valid inequalities for the TSP
From MaRDI portal
Publication:1908019
zbMath0844.90101MaRDI QIDQ1908019
Publication date: 28 February 1996
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
valid inequalitiesworst-case analysispolyhedral combinatoricsgraphical travelling salesman polyhedron
Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)
Related Items
A Fast $$(2 + 2/7)$$-Approximation Algorithm for Capacitated Cycle Covering, A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs, Theoretical challenges towards cutting-plane selection, Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, On the graphical relaxation of the symmetric traveling salesman polytope, Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices, On the relative strength of split, triangle and quadrilateral cuts, Approximating polyhedra with sparse inequalities, 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, A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts, Spanning closed walks and TSP in 3-connected planar graphs, Shorter tours and longer detours: uniform covers and a bit beyond, The traveling salesman problem on cubic and subcubic graphs, Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem, The salesman's improved tours for fundamental classes, Relaxations of mixed integer sets from lattice-free polyhedra, The strongest facets of the acyclic subgraph polytope are unknown, The worst case analysis of strong knapsack facets, 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, Lift-and-project ranks of the set covering polytope of circulant matrices, Relaxations of mixed integer sets from lattice-free polyhedra, Computing compatible tours for the symmetric traveling salesman problem, Simpler analysis of LP extreme points for traveling salesman and survivable network design problems, TSP Tours in Cubic Graphs: Beyond 4/3, The nonidealness index of rank-ideal matrices, Aggregation-based cutting-planes for packing and covering integer programs, On the core of traveling salesman games, The indefinite period traveling salesman problem, Integrality gap of the vertex cover linear programming relaxation, A new integer programming formulation of the graphical traveling salesman problem, Properties of some ILP formulations of a class of partitioning problems, Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes, Computing in combinatorial optimization, Strength of facets for the set covering and set packing polyhedra on circulant matrices, On the facial structure of symmetric and graphical traveling salesman polyhedra, Unnamed Item, Unnamed Item, Approximating TSP walks in subcubic graphs, A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering
