The Traveling Salesman Problem with Distances One and Two
From MaRDI portal
Publication:4697080
DOI10.1287/moor.18.1.1zbMath0778.90057OpenAlexW2141355868WikidataQ56067405 ScholiaQ56067405MaRDI QIDQ4697080
Mihalis Yannakakis, Christos H. Papadimitriou
Publication date: 29 June 1993
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.18.1.1
Programming involving graphs or networks (90C35) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items
Approximation Algorithms for the Traveling Salesman Problem with Range Condition, Improved Lower Bounds on the Approximability of the Traveling Salesman Problem, The hardness of approximation: Gap location, MP or not MP: that is the question, Traveling salesman problems in temporal graphs, Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems, Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem, Performance guarantees for the TSP with a parameterized triangle inequality, Approximation algorithms for the TSP with sharpened triangle inequality, Differential approximation results for the traveling salesman and related problems, On residual approximation in solution extension problems, Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, A survey on combinatorial optimization in dynamic environments, Approximation algorithms for the scaffolding problem and its generalizations, The Steiner traveling salesman problem with online edge blockages, Good triangulations yield good tours, When the greedy algorithm fails, Constant Factor Approximation for ATSP with Two Edge Weights, An Introduction to Temporal Graphs: An Algorithmic Perspective, TRAVELING SALESMAN PROBLEM OF SEGMENTS, On the longest circuit in an alterable digraph, An approximation algorithm for a general class of parametric optimization problems, Weighted amplifiers and inapproximability results for travelling salesman problem, Approximation hardness of graphic TSP on cubic graphs, Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension, Improved approximations for capacitated vehicle routing with unsplittable client demands, A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem, Adversarial patrolling with spatially uncertain alarm signals, Vehicle routing on road networks: how good is Euclidean approximation?, Intractability of assembly sequencing: Unit disks in the plane, Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies, Exponential approximation schemata for some network design problems, Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications, Approximation performance of ant colony optimization for the TSP(1,2) problem, Unnamed Item, Approximating Alternative Solutions, Approximation algorithms for the traveling repairman and speeding deliveryman problems, Labeled traveling salesman problems: complexity and approximation, On the approximability of some degree-constrained subgraph problems, Connected facility location via random facility sampling and core detouring, Approximating the metric TSP in linear time, Not being (super)thin or solid is hard: A study of grid Hamiltonicity, A better differential approximation ratio for symmetric TSP, On testing Hamiltonicity of graphs, Approximately fair cost allocation in metric traveling salesman games, The traveling salesman problem on cubic and subcubic graphs, Better Approximation Algorithms for Scaffolding 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, The on-line asymmetric traveling salesman problem, New Approximation Algorithms for (1,2)-TSP, New inapproximability bounds for TSP, Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem, Approximation algorithms for connected graph factors of minimum weight, Knowing All Optimal Solutions Does Not Help for TSP Reoptimization, TSP on Cubic and Subcubic Graphs, On approximating the longest path in a graph, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Critical hereditary graph classes: a survey, Improved integrality gap upper bounds for traveling salesperson problems with distances one and two, Sequencing and scheduling for filling lines in dairy production, \(\frac{13}{9}\)-approximation for graphic TSP, An approximation algorithm for the asymmetric travelling salesman problem with distances one and two, Approximation algorithms for some vehicle routing problems, An approximation algorithm for the minimum co-path set problem, An improved upper bound for the TSP in cubic 3-edge-connected graphs, Vehicle routing with subtours, On approximating the longest path in a graph, Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s), Unnamed Item, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness, TSP with bounded metrics, The checkpoint problem, A note on a new greedy-solution representation and a new greedy parallelizable heuristic for the traveling salesman problem, The Chinese deliveryman problem, Degree-Constrained Subgraph Problems: Hardness and Approximation Results, Cost-effective designs of fault-tolerant access networks in communication systems, Approximation of the double traveling salesman problem with multiple stacks, Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem, Nontrivial path covers of graphs: existence, minimization and maximization, The maximum binary tree problem, Constant factor approximation for ATSP with two edge weights, The \(m\)-Steiner traveling salesman problem with online edge blockages, The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme, Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2, On Interference Graphs, On the number ofk-cycles in the assignment problem for random matrices, (1,2)-HAMILTONIAN COMPLETION ON A MATCHING, Reoptimization of minimum and maximum traveling salesman's tours, The approximability of the weighted Hamiltonian path completion problem on a tree, An Introduction to Temporal Graphs: An Algorithmic Perspective*, Approximation algorithms for time-dependent orienteering., Reducing Path TSP to TSP, Approximating spanning trees with few branches, Approximation algorithms for some extensions of the maximum profit routing problem, The maximum \(f\)-depth spanning tree problem, Approximating the maximum quadratic assignment problem, Differential approximation results for the traveling salesman problem with distances 1 and 2, Unconstrained traveling tournament problem is APX-complete, Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension, Approximations for the Steiner multicycle problem
