Publication:3931037
From MaRDI portal
zbMath0475.90080MaRDI QIDQ3931037
Publication date: 1978
traveling salesman; approximate algorithm; a priori estimation of relative deviation; complete non-directed graphs; equivalent statements; extremal by-passes
Related Items
The travelling salesman and the PQ-tree, A 3/2-Approximation for the Metric Many-Visits Path TSP, Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, SFCDecomp: Multicriteria Optimized Tool Path Planning in 3D Printing using Space-Filling Curve Based Domain Decomposition, Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem, O(log m)-approximation for the routing open shop problem, Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems, A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem, Improving the approximation ratio for capacitated vehicle routing, Improving the approximation ratio for capacitated vehicle routing, Reducing Path TSP to TSP, An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem, A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP, A deterministic better-than-3/2 approximation algorithm for metric TSP, On approximate data reduction for the Rural Postman Problem: Theory and experiments, The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem, Approximation algorithms with constant factors for a series of asymmetric routing problems, Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles, Approximation of the double traveling salesman problem with multiple stacks, A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing, Approximating TSP walks in subcubic graphs, Learning to sparsify travelling salesman problem instances, Two-machine routing open shop: How long is the optimal makespan?, Matroid-based TSP rounding for half-integral solutions, Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows, Approximation algorithms for some min-max postmen cover problems, Hard to solve instances of the Euclidean traveling salesman problem, A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem, Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP, Improving on best-of-many-Christofides for \(T\)-tours, The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable, An LP-based approximation algorithm for the generalized traveling salesman path problem, Approximation algorithms for multi-vehicle stacker crane problems, Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem, Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio
