A Probabilistic Analysis of Christofides' Algorithm

No abstract is available for this paper.

• Publication year

  2012

• Venue

  Scandinavian Workshop on Algorithm Theory

• Publication date

  2012-07-04

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-31155-0_20
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Traveling Salesman Problem and its Variations

  2014cited by this paper
• Fast minimum-weight double-tree shortcutting for metric TSP: Is the best one good enough?

  2007cited by this paper
• Probabilistic Analysis of the TSP

  2007cited by this paper
• The traveling salesman problem and its variations

  2007cited by this paper
• Probabilistic analysis for a multiple depot vehicle routing problem

  2005cited by this paper
• Probabilistic analysis of the Traveling Salesman Problem to appear as a chapter in a forthcoming book on the TSP

  2002influential reference
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems

  1999cited by this paper
• Probability theory of classical Euclidean optimization problems

  1998influential reference
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

  1998cited by this paper
• Asymptotic experimental analysis for the Held-Karp traveling salesman bound

  1996cited by this paper
• A Matching Problem and Subadditive Euclidean Functionals

  1993cited by this paper
• On: Travelling salesman problem under categorization: Operations Research Letters 12 (1992) 89-95

  1993cited by this paper
• On the Travelling Salesperson Problem in Many Dimensions

  1992cited by this paper
• Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem

  1991cited by this paper
• An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability

  1990cited by this paper
• Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching

  1988cited by this paper
• Growth Rates of Euclidean Minimal Spanning Trees With Power Weighted Edges

  1988cited by this paper
• Probability theory and combinatorial optimization

  1987cited by this paper
• Subadditive Euclidean Functionals and Nonlinear Growth in Geometric Probability

  1981cited by this paper
• CBMS-NSF REGIONAL CONFERENCE SERIES IN APPLIED MATHEMATICS

  1978cited by this paper
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane

  1977cited by this paper
• The shortest path through many points

  1959cited by this paper

• A Near Optimal Approach for Symmetric Traveling Salesman Problem in Euclidean Space

  2017cites this paper
• Obtaining Quality-Proved Near Optimal Results for Traveling Salesman Problem

  2015cites this paper
• Probabilistic analysis of power assignments

  2014influential citation