The Traveling Salesman Problem with Distances One and Two

Christos H. Papadimitriou
Christos H. Papadimitriou
Department of Computer Sciences and Engineering, University of California at San Diego, La Jolla, California 92093-0114
Search for more papers by this author
,
Mihalis Yannakakis
Mihalis Yannakakis
AT&T Bell Laboratories, 600 Mountain Avenue, Room 2C319, Murray Hill, New Jersey 07974-2070
Search for more papers by this author

Christos H. Papadimitriou

Department of Computer Sciences and Engineering, University of California at San Diego, La Jolla, California 92093-0114

Search for more papers by this author

Mihalis Yannakakis

AT&T Bell Laboratories, 600 Mountain Avenue, Room 2C319, Murray Hill, New Jersey 07974-2070

Search for more papers by this author

Published Online:1 Feb 1993https://doi.org/10.1287/moor.18.1.1

Abstract

We present a polynomial-time approximation algorithm with worst-case ratio 7/6 for the special case of the traveling salesman problem in which all distances are either one or two. We also show that this special case of the traveling salesman problem is MAX SNP-hard, and therefore it is unlikely that it has a polynomial-time approximation scheme.

Cited by
- I/O complexity and pebble games with partial computations
  Information Processing Letters, Vol. 194
- Optimum 6G/7G quantum network design: Survey
  Optics Communications, Vol. 608
- Approximating maximum-size properly colored forests
  European Journal of Combinatorics, Vol. 132
- The two-stripe symmetric circulant TSP is in P
  17 April 2025 | Mathematical Programming, Vol. 215, No. 1-2
- Circulant TSP: Vertices of the edge-length polytope and superpolynomial lower bounds
  Discrete Applied Mathematics, Vol. 376
- Improved Approximations for a CVRP with Unsplittable Demands
  Zachary Friggstad,
  Ramin Mousavi,
  Mirmahdi Rahgoshay,
  Mohammad R. Salavatipour
  17 October 2025 | Mathematics of Operations Research, Vol. 0, No. 0
- An evaluation of common modeling choices for the vehicle routing problem with stochastic demands
  European Journal of Operational Research, Vol. 321, No. 1
- Complexity of Fixed Order Routing
  12 February 2025
- Improved approximation algorithms for the k-path partition problem
  13 September 2024 | Journal of Global Optimization, Vol. 90, No. 4
- Approximations for the Steiner Multicycle problem
  Theoretical Computer Science, Vol. 1020
- Framework for Small Traveling Salesman Problems
  12 November 2024 | International Journal on Applied Physics and Engineering, Vol. 3
- On λ $\lambda $‐backbone coloring of cliques with tree backbones in linear time
  29 April 2024 | Journal of Graph Theory, Vol. 107, No. 1
- On a Traveling Salesman Problem for Points in the Unit Cube
  18 July 2024 | Algorithmica, Vol. 86, No. 9
- Travelling salesman paths on Demidenko matrices
  Discrete Applied Mathematics, Vol. 354
- Circulant TSP special cases: Easily-solvable cases and improved approximations
  Operations Research Letters, Vol. 55
- On approximating a new generalization of traveling salesman problem
  Heliyon, Vol. 10, No. 10
- IntroUNET: Identifying introgressed alleles via semantic segmentation
  20 February 2024 | PLOS Genetics, Vol. 20, No. 2
- Recognising permuted Demidenko matrices
  Operations Research Letters, Vol. 51, No. 5
- Unconstrained traveling tournament problem is APX-complete
  Operations Research Letters, Vol. 51, No. 4
- Approximation algorithms for some extensions of the maximum profit routing problem
  6 December 2022 | Journal of Combinatorial Optimization, Vol. 45, No. 1
- Low Treewidth Embeddings of Planar and Minor-Free Metrics
- Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension
  16 June 2021 | Optimization Letters, Vol. 16, No. 7
- An approximation algorithm for a general class of parametric optimization problems
  22 September 2020 | Journal of Combinatorial Optimization, Vol. 43, No. 5
- Weighted amplifiers and inapproximability results for Travelling Salesman problem
  19 October 2020 | Journal of Combinatorial Optimization, Vol. 43, No. 5
- Bypassing the surface embedding: approximation schemes for network design in minor-free graphs
  10 June 2022
- Reducing Path TSP to TSP
  18 October 2021 | SIAM Journal on Computing, Vol. 51, No. 3
- Improved Approximations for Capacitated Vehicle Routing with Unsplittable Client Demands
  27 May 2022
- Approximations for the Steiner Multicycle Problem
  29 October 2022
- Optimal Scheduling of the Leaves of a Tree and the SVO Frequencies of Languages
  5 February 2023
- Time complexity analysis of evolutionary algorithms for 2-hop (1,2)-minimum spanning tree problem
  Theoretical Computer Science, Vol. 893
- The Maximum Binary Tree Problem
  31 May 2021 | Algorithmica, Vol. 83, No. 8
- Approximation of the Double Traveling Salesman Problem with Multiple Stacks
  Theoretical Computer Science, Vol. 877
- A 43 -approximation algorithm for the Maximum Internal Spanning Tree Problem
  Journal of Computer and System Sciences, Vol. 118
- The m-Steiner Traveling Salesman Problem with online edge blockages
  23 March 2021 | Journal of Combinatorial Optimization, Vol. 41, No. 4
- Vehicle routing on road networks: How good is Euclidean approximation?
  Computers & Operations Research, Vol. 129
- On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
- The Chinese deliveryman problem
  19 October 2019 | 4OR, Vol. 18, No. 3
- The node weight dependent traveling salesperson problem
  26 June 2020
- Nontrivial path covers of graphs: existence, minimization and maximization
  30 November 2019 | Journal of Combinatorial Optimization, Vol. 39, No. 2
- Maximizing the Number of Spanning Trees in a Connected Graph
  IEEE Transactions on Information Theory, Vol. 66, No. 2
- Replica symmetry and replica symmetry breaking for the traveling salesperson problem
  23 September 2019 | Physical Review E, Vol. 100, No. 3
- Vehicle routing with subtours
  Discrete Optimization, Vol. 33
- Reoptimization of minimum latency problem revisited: don’t panic when asked to revisit the route after local modifications
  11 June 2018 | Journal of Combinatorial Optimization, Vol. 37, No. 2
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
  12 February 2019 | Algorithms, Vol. 12, No. 2
- A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs
  12 July 2019
- Approximation Hardness of Travelling Salesman via Weighted Amplifiers
  21 July 2019
- Exponential Time Approximation Scheme for TSP
  1 August 2019
- Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
  17 December 2019 | SIAM Journal on Discrete Mathematics, Vol. 33, No. 4
- Constant factor approximation for ATSP with two edge weights
  12 September 2017 | Mathematical Programming, Vol. 172, No. 1-2
- On residual approximation in solution extension problems
  12 November 2017 | Journal of Combinatorial Optimization, Vol. 36, No. 4
- Approximation algorithms for the scaffolding problem and its generalizations
  Theoretical Computer Science, Vol. 734
- Improved integrality gap upper bounds for traveling salesperson problems with distances one and two
  European Journal of Operational Research, Vol. 266, No. 2
- Approximation Algorithms for Connected Graph Factors of Minimum Weight
  16 November 2016 | Theory of Computing Systems, Vol. 62, No. 2
- Some Easy and Some Not so Easy Geometric Optimization Problems
  29 November 2018
- Approximation Algorithms
  14 March 2018
- The Traveling Salesman Problem
  14 March 2018
- Approximationsalgorithmen
  25 July 2018
- Das Traveling-Salesman-Problem
  25 July 2018
- Minimizing Latency in Online Ride and Delivery Services
- Vertex-disjoint path covers in graphs
  2 July 2017
- Adversarial patrolling with spatially uncertain alarm signals
  Artificial Intelligence, Vol. 246
- A 4/5 - Approximation Algorithm for the Maximum Traveling Salesman Problem
  24 May 2017
- Reoptimization of Minimum Latency Problem
  1 July 2017
- Critical hereditary graph classes: a survey
  26 December 2015 | Optimization Letters, Vol. 10, No. 8
- Approximation performance of ant colony optimization for the TSP(1,2) problem
  6 August 2015 | International Journal of Computer Mathematics, Vol. 93, No. 10
- An Introduction to Temporal Graphs: An Algorithmic Perspective *
  14 April 2016 | Internet Mathematics, Vol. 12, No. 4
- Traveling salesman problems in temporal graphs
  Theoretical Computer Science, Vol. 634
- A 3D printing path optimizer based on Christofides algorithm
- MP or not MP: that is the question
  3 November 2015 | Journal of Scheduling, Vol. 19, No. 1
- Constant Factor Approximation for ATSP with Two Edge Weights
  25 May 2016
- Better Approximation Algorithms for Scaffolding Problems
  27 May 2016
- Integrating Sequencing and Scheduling: A Generic Approach with Two Exemplary Industrial Applications
  11 November 2016
- The TSP-approach to approximate solving the m-Cycles Cover Problem
- The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
  SIAM Journal on Computing, Vol. 45, No. 4
- New inapproximability bounds for TSP
  Journal of Computer and System Sciences, Vol. 81, No. 8
- The Steiner Traveling Salesman Problem with online edge blockages
  European Journal of Operational Research, Vol. 243, No. 1
- On the integrality gap of the subtour LP for the 1,2-TSP
  12 November 2014 | Mathematical Programming, Vol. 150, No. 1
- Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies
  4 August 2015
- An Introduction to Temporal Graphs: An Algorithmic Perspective
  22 November 2015
- Maximum ATSP with Weights Zero and One via Half-Edges
  13 January 2016
- Approximating Spanning Trees with Few Branches
  15 June 2014 | Theory of Computing Systems, Vol. 56, No. 1
- On testing Hamiltonicity of graphs
  Discrete Mathematics, Vol. 338, No. 1
- $\frac{13}{9}$ -Approximation for Graphic TSP
  7 December 2012 | Theory of Computing Systems, Vol. 55, No. 4
- 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
  11 November 2014 | Combinatorica, Vol. 34, No. 5
- Maximum Quadratic Assignment Problem
  13 August 2014 | ACM Transactions on Algorithms, Vol. 10, No. 4
- General Bibliography
  8 August 2014
- Polynomial Approximation
  8 August 2014
- Inapproximability of Combinatorial Optimization Problems
  8 August 2014
- Polynomial Approximation for Multicriteria Combinatorial Optimization Problems
  8 August 2014
- The Traveling Salesman Problem and its Variations
  8 August 2014
- The traveling salesman problem on cubic and subcubic graphs
  21 December 2012 | Mathematical Programming, Vol. 144, No. 1-2
- Guest column
  17 March 2014 | ACM SIGACT News, Vol. 45, No. 1
- The Shortest Superstring Problem
  8 May 2014
- Approximability of Connected Factors
- Traveling Salesman Problems in Temporal Graphs
- On the m-capacitated peripatetic salesman problem with capacity restrictions
  6 March 2014 | Journal of Applied and Industrial Mathematics, Vol. 8, No. 1
- Persistent monitoring in discrete environments: Minimizing the maximum weighted latency between observations
  4 October 2013 | The International Journal of Robotics Research, Vol. 33, No. 1
- Exponential approximation schemata for some network design problems
  Journal of Discrete Algorithms, Vol. 22
- VRP12 (vehicle routing problem with distances one and two) with side constraints
  International Journal of Production Economics, Vol. 144, No. 2
- Optimization of laminate stacking sequence for minimizing weight and cost using elitist ant system optimization
  Advances in Engineering Software, Vol. 57
- Polynomial Approximation
  13 February 2013
- Inapproximability of Combinatorial Optimization Problems
  13 February 2013
- Polynomial Approximation for Multicriteria Combinatorial Optimization Problems
  13 February 2013
- The Traveling Salesman Problem and its Variations
  13 February 2013
- Routing Protocols in Infrastructure-Based Opportunistic Networks
  4 May 2013
- A Hard Problem: The TSP
- Min-Max Latency Walks: Approximation Algorithms for Monitoring Vertex-Weighted Graphs
- New Inapproximability Bounds for TSP
- Finding 2-Factors Closer to TSP Tours in Cubic Graphs
  SIAM Journal on Discrete Mathematics, Vol. 27, No. 2
- (1,2)-HAMILTONIAN COMPLETION ON A MATCHING
  13 May 2013 | International Journal of Foundations of Computer Science, Vol. 24, No. 01
- The checkpoint problem
  Theoretical Computer Science, Vol. 452
- On the approximability of some degree-constrained subgraph problems
  Discrete Applied Mathematics, Vol. 160, No. 12
- Approximation algorithms for the maximum 2-peripatetic salesman problem
  26 August 2012 | Journal of Applied and Industrial Mathematics, Vol. 6, No. 3
- The traveling salesman problem
  19 May 2012
- Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems
  22 April 2011 | Algorithmica, Vol. 62, No. 3-4
- An approximation algorithm for the minimum two peripatetic salesmen problem with different weight functions
  31 May 2012 | Journal of Applied and Industrial Mathematics, Vol. 6, No. 2
- Approximation Algorithms
  27 October 2011
- The Traveling Salesman Problem
  27 October 2011
- Approximationsalgorithmen
  4 May 2012
- Das Traveling-Salesman-Problem
  4 May 2012
- On the Integrality Gap of the Subtour LP for the 1,2-TSP
- Improved Inapproximability for TSP
- Light Spanners in Bounded Pathwidth Graphs
- Approximating TSP on Metrics with Bounded Global Growth
  SIAM Journal on Computing, Vol. 41, No. 3
- Approximating the Metric TSP in Linear Time
  18 August 2010 | Theory of Computing Systems, Vol. 49, No. 3
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Approximation algorithms and heuristics for a 2‐depot, heterogeneous Hamiltonian path problem
  25 February 2011 | International Journal of Robust and Nonlinear Control, Vol. 21, No. 12
- An Approximation Algorithm for the Minimum Co-Path Set Problem
  21 January 2010 | Algorithmica, Vol. 60, No. 4
- Sequencing and scheduling for filling lines in dairy production
  17 May 2011 | Optimization Letters, Vol. 5, No. 3
- Knowing All Optimal Solutions Does Not Help for TSP Reoptimization
- TSP on Cubic and Subcubic Graphs
- Externalities among Advertisers in Sponsored Search
- Algoritmi approssimati
- Il problema del commesso viaggiatore
- Parameterized Complexity of Arc-Weighted Directed Steiner Problems
  SIAM Journal on Discrete Mathematics, Vol. 25, No. 2
- Connected facility location via random facility sampling and core detouring
  Journal of Computer and System Sciences, Vol. 76, No. 8
- Approximability of the Multiple Stack TSP
  Electronic Notes in Discrete Mathematics, Vol. 36
- Labeled Traveling Salesman Problems: Complexity and approximation
  Discrete Optimization, Vol. 7, No. 1-2
- Algorithmes d’approximation
- Le probléme du voyageur de commerce
- Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm
- Reoptimization of minimum and maximum traveling salesman's tours
  Journal of Discrete Algorithms, Vol. 7, No. 4
- Not being (super)thin or solid is hard: A study of grid Hamiltonicity
  Computational Geometry, Vol. 42, No. 6-7
- Cost‐effective designs of fault‐tolerant access networks in communication systems
  13 February 2009 | Networks, Vol. 53, No. 4
- Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
  Discrete Applied Mathematics, Vol. 157, No. 9
- Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
  Operations Research Letters, Vol. 37, No. 3
- On Interference Graphs
  Electronic Notes in Discrete Mathematics, Vol. 33
- Degree-Constrained Subgraph Problems: Hardness and Approximation Results
- Approximation Polynomial Algorithms for Some Modifications of TSP
  2 April 2009
- A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
- Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2
  18 March 2009 | Journal of Applied and Industrial Mathematics, Vol. 3, No. 1
- Approximately Fair Cost Allocation in Metric Traveling Salesman Games
  21 December 2007 | Theory of Computing Systems, Vol. 43, No. 1
- The on-line asymmetric traveling salesman problem
  Journal of Discrete Algorithms, Vol. 6, No. 2
- Exploiting planarity in separation routines for the symmetric traveling salesman problem
  Discrete Optimization, Vol. 5, No. 2
- A better differential approximation ratio for symmetric TSP
  Theoretical Computer Science, Vol. 396, No. 1-3
- On the number of k -cycles in the assignment problem for random matrices
  31 March 2008 | Journal of Statistical Mechanics: Theory and Experiment, Vol. 2008, No. 03
- Good triangulations yield good tours
  Computers & Operations Research, Vol. 35, No. 2
- Approximation of Multi‐criteria Min and Max TSP (1, 2)
  3 February 2010
- Approximating Alternative Solutions
- Approximation Algorithms
- The Traveling Salesman Problem
- Approximationsalgorithmen
- Das Traveling-Salesman-Problem
- On Labeled Traveling Salesman Problems
- Combinatorial Optimization with Explicit Delineation of the Ground Set by a Collection of Subsets
  SIAM Journal on Discrete Mathematics, Vol. 21, No. 4
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
  SIAM Journal on Computing, Vol. 37, No. 6
- A Faster, Better Approximation Algorithm for the Minimum Latency Problem
  SIAM Journal on Computing, Vol. 37, No. 5
- Polynomial Algorithms for Some Hard Problems of Finding Connected Spanning Subgraphs of Extreme Total Edge Weight
- Approximating the Maximum Sharing Problem
- Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows
- TSP with bounded metrics
  Journal of Computer and System Sciences, Vol. 72, No. 4
- Approximate Fair Cost Allocation in Metric Traveling Salesman Games
- A Survey of Approximation Results for Local Search Algorithms
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
- On Approximating the Maximum Simple Sharing Problem
- Approximation Algorithms
- The Traveling Salesman Problem
- Polynomial approximation algorithms with performance guarantees: An introduction-by-example
  European Journal of Operational Research, Vol. 165, No. 3
- An improved upper bound for the TSP in cubic 3-edge-connected graphs
  Operations Research Letters, Vol. 33, No. 5
- The approximability of the weighted Hamiltonian path completion problem on a tree
  Theoretical Computer Science, Vol. 341, No. 1-3
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
  Theoretical Computer Science, Vol. 339, No. 2-3
- A TSP (1,2) application arising in cable assembly shops
  21 December 2017 | Journal of the Operational Research Society, Vol. 56, No. 6
- Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
  European Journal of Operational Research, Vol. 161, No. 3
- Approximation algorithms for some vehicle routing problems
  Discrete Applied Mathematics, Vol. 146, No. 1
- Probabilistic Verification and Non-Approximability
- The On-line Asymmetric Traveling Salesman Problem
- Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems
- (Non)-Approximability for the Multi-criteria TSP(1,2)
- Approximation Results for the Weighted P 4 Partition Problems
- An Improved Approximation Algorithm for TSP with Distances One and Two
- A General Framework for Coloring Problems: Old Results, New Results, and Open Problems
- A linear-time approximation scheme for planar weighted TSP
- When the greedy algorithm fails
  Discrete Optimization, Vol. 1, No. 2
- Thomas Hanne
  Top, Vol. 12, No. 1
- TRAVELING SALESMAN PROBLEM OF SEGMENTS
  20 November 2011 | International Journal of Computational Geometry & Applications, Vol. 14, No. 01n02
- A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One
- An -approximation algorithm for the asymmetric maximum TSP
  Journal of Algorithms, Vol. 50, No. 1
- Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem
  Theoretical Computer Science, Vol. 310, No. 1-3
- Radio Labeling with Preassigned Frequencies
  SIAM Journal on Optimization, Vol. 15, No. 1
- The geometric maximum traveling salesman problem
  1 September 2003 | Journal of the ACM, Vol. 50, No. 5
- Differential approximation results for the traveling salesman problem with distances 1 and 2
  European Journal of Operational Research, Vol. 145, No. 3
- Differential Approximation for Some Routing Problems
  13 May 2003
- Traveling Salesman Problem of Segments
  24 June 2003
- Approximating the Pareto Curve with Local Search for the Bicriteria TSP(1,2) Problem
- Paths, trees, and minimum latency tours
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
- Approximation Schemes for Minimum Latency Problems
  SIAM Journal on Computing, Vol. 32, No. 5
- A 5/8 Approximation Algorithm for the Maximum Asymmetric TSP
  SIAM Journal on Discrete Mathematics, Vol. 17, No. 2
- Approximation algorithms for time-dependent orienteering
  Information Processing Letters, Vol. 83, No. 2
- Differential approximation results for the traveling salesman and related problems
  Information Processing Letters, Vol. 82, No. 5
- Radio Labeling with Pre-assigned Frequencies
  29 August 2002
- Hardness of Approximation for Vertex-Connectivity Network-Design Problems
  4 October 2002
- Approximation Algorithms
- The Traveling Salesman Problem
- A note on a new greedy-solution representation and a new greedy parallelizable heuristic for the traveling salesman problem
  Chaos, Solitons & Fractals, Vol. 13, No. 1
- Improved Approximation Lower Bounds for TSP with Distances One and Two
  Interdisciplinary Information Sciences, Vol. 8, No. 1
- z-Approximations
  Journal of Algorithms, Vol. 41, No. 2
- The maximum f-depth spanning tree problem
  Information Processing Letters, Vol. 80, No. 4
- Differential Approximation Results for the Traveling Salesman Problem with Distances 1 and 2
  2 August 2001
- Approximating Bounded Degree Instances of NP-Hard Problems
  2 August 2001
- Approximation Algorithms for Time-Dependent Orienteering
  2 August 2001
- Computing Cycle Covers without Short Cycles
  17 August 2001
- The UPS Problem
  16 March 2001
- Approximation Hardness of TSP with Bounded Metrics
  4 July 2001
- Approximating the maximum quadratic assignment problem
  Information Processing Letters, Vol. 77, No. 1
- Approximation algorithms for the TSP with sharpened triangle inequality
  Information Processing Letters, Vol. 75, No. 3
- Approximation Algorithms for the Traveling Salesman Problem with Range Condition
  15 April 2002 | RAIRO - Theoretical Informatics and Applications, Vol. 34, No. 3
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
  15 April 2002 | RAIRO - Theoretical Informatics and Applications, Vol. 34, No. 3
- On the approximability of the traveling salesman problem (extended abstract)
  1 May 2000
- An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree
  29 January 2002
- Approximate TSP in Graphs with Forbidden Minors
  18 February 2002
- Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem
  14 February 2000
- An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality
  24 March 2000
- Approximation Algorithms
- The Traveling Salesman Problem
- Performance guarantees for the TSP with a parameterized triangle inequality
  Information Processing Letters, Vol. 73, No. 1-2
- When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree
  SIAM Journal on Computing, Vol. 30, No. 2
- Approximating minimum spanning tree of depth 2
  24 August 2006 | International Transactions in Operational Research, Vol. 6, No. 6
- COMPLEXITY MEASURES FOR ASSEMBLY SEQUENCES
  20 November 2011 | International Journal of Computational Geometry & Applications, Vol. 09, No. 04n05
- On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
  Journal of Algorithms, Vol. 31, No. 1
- Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2
- Performance Guarantees for the TSP with a Parameterized Triangle Inequality
  18 July 2002
- Physical Mapping with Repeated Probes: The Hypergraph Superstring Problem
  8 July 1999
- An Explicit Lower Bound for TSP with Distances One and Two
  12 April 2002
- A Better Approximation Algorithm for Finding Planar Subgraphs
  Journal of Algorithms, Vol. 27, No. 2
- Proof verification and the hardness of approximation problems
  1 May 1998 | Journal of the ACM, Vol. 45, No. 3
- Probabilistic analysis of 2-opt for travelling salesman problems
  International Journal of Systems Science, Vol. 29, No. 3
- The Maximum Traveling Salesman Problem Under Polyhedral Norms
  18 June 1998
- A Hamiltonian Approach to the Assignment of Non-reusable Frequencies
- On the approximation of finding A(nother) Hamiltonian cycle in cubic Hamiltonian graphs
  20 June 2005
- On Syntactic versus Computational Views of Approximability
  SIAM Journal on Computing, Vol. 28, No. 1
- A survey of approximately optimal solutions to some covering and packing problems
  1 June 1997 | ACM Computing Surveys, Vol. 29, No. 2
- On approximating the longest path in a graph
  Algorithmica, Vol. 18, No. 1
- Intractability of assembly sequencing: Unit disks in the plane
  30 July 2005
- Maximum travelling salesman problem
  Mathematical Methods of Operations Research, Vol. 43, No. 2
- Searching a fixed graph
  2 June 2005
- On the longest circuit in an alterable digraph
  Journal of Global Optimization, Vol. 7, No. 3
- On the Complexity of Min-Max Optimization Problems and their Approximation
- An approximation scheme for planar graph TSP
- Linear approximation of shortest superstrings
  1 July 1994 | Journal of the ACM, Vol. 41, No. 4
- The hardness of approximation: Gap location
  Computational Complexity, Vol. 4, No. 2
- A Methodology for Optimizing Selling Time of Salespersons
  21 December 2015 | Journal of Marketing Theory and Practice, Vol. 2, No. 2
- Some open problems in approximation
  26 May 2005
- Transparent Proofs and Limits to Approximation
- Transparent Proofs and Limits to Approximation
- Long tours and short superstrings
- On syntactic versus computational views of approximability
- Recent developments on the approximability of combinatorial problems
  1 June 2005
- The hardness of approximation: gap location
- The NP-completeness column: An ongoing guide
  Journal of Algorithms, Vol. 13, No. 3
- Proof verification and hardness of approximation problems

cover image Mathematics of Operations Research

Volume 18, Issue 1

February 1993

Pages 1-253

Article Information

Metrics

Information

Published Online:February 01, 1993

Cite as

Christos H. Papadimitriou, Mihalis Yannakakis, (1993) The Traveling Salesman Problem with Distances One and Two. Mathematics of Operations Research 18(1):1-11.

https://doi.org/10.1287/moor.18.1.1

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

The Traveling Salesman Problem with Distances One and Two

Abstract

Volume 18, Issue 1

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News