Heuristic analysis, linear programming and branch and bound

DOI10.1007/BFb0120913zbMath0442.90061MaRDI QIDQ3885519

Publication date: 1980

Published in: Mathematical Programming Studies (Search for Journal in Brave)

dynamic programming heuristic algorithms travelling salesman branch and bound algorithms bin packing cutting stock multidimensional knapsack problem enumeration schemes Benders' algorithm Eulerian tours duality gaps worst case behaviour longest Hamiltonian tour matching heuristic uncapacitated K-location problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Integer programming (90C10) Linear programming (90C05) Eulerian and Hamiltonian graphs (05C45)

Related Items

Approximation Limits of Linear Programs (Beyond Hierarchies), Network design with edge-connectivity and degree constraints, A 3/2-Approximation for the Metric Many-Visits Path TSP, Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem, A new class of cutting planes for the symmetric travelling salesman problem, Approximation algorithms for inventory problems with submodular or routing costs, Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, Matroid-based TSP rounding for half-integral solutions, The parsimonious property of cut covering problems and its applications, A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem, Improving on best-of-many-Christofides for $T$-tours, The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem, On approximately fair cost allocation in Euclidean TSP games, A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case, Robust Algorithms for TSP and Steiner Tree, A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP, Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices, 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, 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, Heuristics and their design: A survey, Analyzing the Held-Karp TSP bound: A monotonicity property with application, The multidimensional 0-1 knapsack problem: an overview., 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, 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, Approximation algorithms for metric tree cover and generalized tour and tree covers, Approximation algorithms for connected graph factors of minimum weight, Online covering salesman problem, TSP on Cubic and Subcubic Graphs, Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems, Improved approximation algorithms for MAX $k$-cut and MAX BISECTION, Hard to solve instances of the Euclidean traveling salesman problem, A note on the prize collecting traveling salesman problem, Improved integrality gap upper bounds for traveling salesperson problems with distances one and two, Survivable networks, linear programming relaxations and the parsimonious property, $\frac{13}{9}$-approximation for graphic TSP, Deterministic sampling algorithms for network design, An improved upper bound for the TSP in cubic 3-edge-connected graphs, Unnamed Item, TSP Tours in Cubic Graphs: Beyond 4/3, Preprocessing composite cutting procedure: an approach to the integer model, On the integrality ratio of the subtour LP for Euclidean TSP, A minimum spanning tree based heuristic for the travelling salesman tour, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem, Reassembling Trees for the Traveling Salesman, An improved upper bound on the integrality ratio for the $s$-$t$-path TSP, Improving the approximation ratio for capacitated vehicle routing, Unnamed Item, A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem, Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes, An elementary survey of general duality theory in mathematical programming, An improved approximation ratio for the minimum latency problem, Estimating the Held-Karp lower bound for the geometric TSP, On the Greedy Heuristic for Continuous Covering and Packing Problems, Unnamed Item, On some approximately balanced combinatorial cooperative games, LP-based algorithms for multistage minimization problems, The multidimensional 0-1 knapsack problem -- bounds and computational aspects