scientific article
From MaRDI portal
Publication:3931037
zbMath0475.90080MaRDI QIDQ3931037
Publication date: 1978
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
traveling salesmanapproximate algorithma priori estimation of relative deviationcomplete non-directed graphsequivalent statementsextremal by-passes
Related Items (35)
A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps ⋮ Matroid-based TSP rounding for half-integral solutions ⋮ 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 ⋮ Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows ⋮ SFCDecomp: Multicriteria Optimized Tool Path Planning in 3D Printing using Space-Filling Curve Based Domain Decomposition ⋮ 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 ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman 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 ⋮ 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 Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems ⋮ Approximation algorithms for some min-max postmen cover problems ⋮ The travelling salesman and the PQ-tree ⋮ Hard to solve instances of the Euclidean traveling salesman problem ⋮ A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem ⋮ Approximation of the double traveling salesman problem with multiple stacks ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing ⋮ Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio ⋮ O(log m)-approximation for the routing open shop problem ⋮ Reducing Path TSP to TSP ⋮ Approximating TSP walks in subcubic graphs ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem ⋮ Learning to sparsify travelling salesman problem instances ⋮ Two-machine routing open shop: How long is the optimal makespan?
This page was built for publication:
