Christofides algorithm

Christofides algorithm

The goal of the Christofides heuristic algorithm (named after Nicos Christofides) is to find a solution to the instances of the traveling salesman problem where the edge weights satisfy the triangle inequality. Let G = (V,w) be an instance of TSP, i.e. G is a complete graph on the set V of vertices with weight function w assigning a nonnegative real weight to every edge of G.

Pseudo-code:
Step 1: Create the minimum spanning tree MST T of G.
Step 2: Let O be the set of vertices with odd degree in T and find a perfect matching M with minimum weight in the complete graph over the vertices from O.
Step 3: Combine the edges of M and T to form a multigraph H.
Step 4: Form an Eulerian circuit in H (H is Eulerian because it is connected, with only even-degree vertices).
Step 5: Make the circuit found in previous step Hamiltonian by skipping visited nodes (shortcutting).

Approximation ratio

The cost of the solution produced by the algorithm is within 3/2 of the optimum.

The proof is as follows:

Let A denote the edge set of the optimal solution of TSP for G. Because (V,A) is connected, it contains some spanning tree T and thus w(A)w(T). Further let B denote the edge set of the optimal solution of TSP for the complete graph over vertices from O. Because the edge weights are triangular (so visiting more nodes cannot reduce total cost), we know that w(A)w(B). We show that there is a perfect matching of vertices from O with weight under w(A)/2w(B)/2 and therefore we have the same upper bound for M (because M is a perfect matching of minimum cost). Because O must contain an even number of vertices, a perfect matching exists. Let e1,...,e2k be the (only) Eulerian path in (O,B). Clearly both e1,e3,...,e2k-1 and e2,e4,...,e2k are perfect matchings and the weight of at least one of them is less than or equal to w(B)/2. Thus w(M)+w(T)w(A) + w(A)/2 and from the triangle inequality it follows that the algorithm is 3/2-approximative.

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • APX — For other uses, see APX (disambiguation). In complexity theory the class APX (an abbreviation of approximable ) is the set of NP optimization problems that allow polynomial time approximation algorithms with approximation ratio bounded by a… …   Wikipedia

  • Directed acyclic graph — An example of a directed acyclic graph In mathematics and computer science, a directed acyclic graph (DAG i …   Wikipedia

  • 2-opt — K Opt Heuristiken sind eine Klasse von Algorithmen zum näherungsweisen Lösen des Problems des Handlungsreisenden (PdH). Die k Opt Heuristiken gehören zu den Post Optimization Algorithmen (engl.: Nach Optimierung), die sich dadurch auszeichnen,… …   Deutsch Wikipedia

  • K-Opt-Heuristik — K Opt Heuristiken sind eine Klasse von Algorithmen zum näherungsweisen Lösen des Problems des Handlungsreisenden (PdH). Die k Opt Heuristiken gehören zu den Post Optimization Algorithmen (engl.: Nach Optimierung), die sich dadurch auszeichnen,… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”