Heuristic analysis, linear programming and branch and bound

Cited in

(73)

A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
A new class of cutting planes for the symmetric travelling salesman problem
Heuristics and their design: A survey
An improved approximation ratio for the minimum latency problem
Estimating the Held-Karp lower bound for the geometric TSP
The parsimonious property of cut covering problems and its applications
On approximately fair cost allocation in Euclidean TSP games
The multidimensional 0-1 knapsack problem: an overview.
Approximation algorithms for connected graph factors of minimum weight
Online covering salesman problem
Improved integrality gap upper bounds for traveling salesperson problems with distances one and two
On the integrality ratio of the subtour LP for Euclidean TSP
Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
LP-based algorithms for multistage minimization problems
Matroid-based TSP rounding for half-integral solutions
Shorter tours and longer detours: uniform covers and a bit beyond
The salesman's improved tours for fundamental classes
Hard to solve instances of the Euclidean traveling salesman problem
$\frac{13}{9}$-approximation for graphic TSP
An improved upper bound on the integrality ratio for the $s$-$t$-path TSP
The traveling salesman problem on cubic and subcubic graphs
Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem
An improved upper bound for the TSP in cubic 3-edge-connected graphs
A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
Improving on best-of-many-Christofides for $T$-tours
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
Reassembling trees for the traveling salesman
Approximation algorithms for metric tree cover and generalized tour and tree covers
TSP on cubic and subcubic graphs
On some approximately balanced combinatorial cooperative games
scientific article; zbMATH DE number 6347354 (Why is no real title available?)
Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
Approximation algorithms for inventory problems with submodular or routing costs
Approximation Limits of Linear Programs (Beyond Hierarchies)
Preprocessing composite cutting procedure: an approach to the integer model
An elementary survey of general duality theory in mathematical programming
Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem
On the Greedy Heuristic for Continuous Covering and Packing Problems
Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
A 3/2-Approximation for the Metric Many-Visits Path TSP
Towards improving Christofides algorithm for half-integer TSP
Semidefinite programming relaxations of the traveling salesman problem and their integrality gaps
A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem
TSP tours in cubic graphs: beyond 4/3
Deterministic sampling algorithms for network design
A proof of the Boyd-Carr conjecture
Improving the approximation ratio for capacitated vehicle routing
Robust Algorithms for TSP and Steiner Tree
A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
On the generation of metric TSP instances with a large integrality gap by branch-and-cut
Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles
An improved approximation guarantee for prize-collecting TSP
Matroid-based TSP rounding for half-integral solutions
Improved approximation algorithms for MAX k-cut and MAX BISECTION
A note on the prize collecting traveling salesman problem
Survivable networks, linear programming relaxations and the parsimonious property
A (3/2+1/e)-approximation algorithm for ordered TSP
Improved guarantees for the a priori TSP
A $\frac{4}{3} $-approximation algorithm for half-integral cycle cut instances of the TSP
Lower bounds on the integrality ratio of the subtour LP for the traveling salesman problem
A lower bound for the max entropy algorithm for TSP
A lower bound for the max entropy algorithm for TSP
A minimum spanning tree based heuristic for the travelling salesman tour
Enhanced approximation algorithms for the capacitated location routing problem
New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
Constant-ratio polynomial time approximation of the asymmetric minimum weight cycle cover problem with limited number of cycles
Maximum entropy is a 10/7-approximation algorithm for the TSP on half-integral cycle cut instances
The multidimensional 0-1 knapsack problem -- bounds and computational aspects
Network design with edge-connectivity and degree constraints
Analyzing the Held-Karp TSP bound: A monotonicity property with application

This page was built for publication: Heuristic analysis, linear programming and branch and bound

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