About: Christofides algorithm     Goto   Sponge   Distinct   Permalink

An Entity of Type : dbo:Software, within Data Space : el.dbpedia.org associated with source document(s)

The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality).It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and , who discovered it independently in 1976.

AttributesValues
rdf:type
rdfs:label
  • Christofides algorithm (en)
rdfs:comment
  • The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality).It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and , who discovered it independently in 1976. (en)
sameAs
dbp:wikiPageUsesTemplate
Subject
Link from a Wikipage to an external page
thumbnail
foaf:depiction
  • http://commons.wikimedia.org/wiki/Special:FilePath/Christofides_MST.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/Christofides_Matching.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/Eulertour.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/Eulertour_bereinigt.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/G_V'.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/Metrischer_Graph_mit_5_Knoten.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/TuM.svg
  • http://commons.wikimedia.org/wiki/Special:FilePath/V'.svg
gold:hypernym
prov:wasDerivedFrom
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
Link from a Wikipage to another Wikipage
has abstract
  • The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality).It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and , who discovered it independently in 1976. This algorithm still stands as the best polynomial time approximation algorithm that has been thoroughly peer-reviewed by the relevant scientific community for the traveling salesman problem on general metric spaces. In July 2020 however, Karlin, Klein, and Gharan released a preprint in which they introduced a novel approximation algorithm and claimed that its approximation ratio is 1.5 − 10−36. Their method follows similar principles to Christofides' algorithm, but uses a randomly chosen tree from a carefully chosen random distribution in place of the minimum spanning tree. (en)
foaf:isPrimaryTopicOf
is Wikipage redirect of
is Link from a Wikipage to another Wikipage of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git151 as of Feb 20 2025


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software