Data Portal @ linkeddatafragments.org

Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Travelling_salesman_problem> ?p ?o. }

• Travelling_salesman_problem abstract "The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.TSP is a special case of the travelling purchaser problem.In the theory of computational complexity, the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems. Thus, it is possible that the worst-case running time for any algorithm for the TSP increases superpolynomially (or perhaps exponentially) with the number of cities.The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of 1%.The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows may be imposed.".
• Travelling_salesman_problem thumbnail William_Rowan_Hamilton_painting.jpg?width=300.
• Travelling_salesman_problem wikiPageExternalLink TSPLIB95.
• Travelling_salesman_problem wikiPageExternalLink TravelingSalesmanProblem.
• Travelling_salesman_problem wikiPageExternalLink jps.
• Travelling_salesman_problem wikiPageExternalLink TSP.
• Travelling_salesman_problem wikiPageExternalLink tsp.r-forge.r-project.org.
• Travelling_salesman_problem wikiPageExternalLink tspsg.info.
• Travelling_salesman_problem wikiPageExternalLink tspcodes_link.html.
• Travelling_salesman_problem wikiPageExternalLink LKH.
• Travelling_salesman_problem wikiPageExternalLink tsp.
• Travelling_salesman_problem wikiPageExternalLink index.html.
• Travelling_salesman_problem wikiPageExternalLink tt1801123.
• Travelling_salesman_problem wikiPageExternalLink TSPLIB95.
• Travelling_salesman_problem wikiPageExternalLink concorde.html.
• Travelling_salesman_problem wikiPageExternalLink index.html.
• Travelling_salesman_problem wikiPageExternalLink ~lh71.
• Travelling_salesman_problem wikiPageID "31248".
• Travelling_salesman_problem wikiPageRevisionID "606411437".
• Travelling_salesman_problem hasPhotoCollection Travelling_salesman_problem.
• Travelling_salesman_problem subject Category:Computational_problems_in_graph_theory.
• Travelling_salesman_problem subject Category:Graph_algorithms.
• Travelling_salesman_problem subject Category:Hamiltonian_paths_and_cycles.
• Travelling_salesman_problem subject Category:NP-complete_problems.
• Travelling_salesman_problem subject Category:Operations_research.
• Travelling_salesman_problem subject Category:Travelling_salesman_problem.
• Travelling_salesman_problem type Abstraction100002137.
• Travelling_salesman_problem type Act100030358.
• Travelling_salesman_problem type Action100037396.
• Travelling_salesman_problem type Activity100407535.
• Travelling_salesman_problem type Algorithm105847438.
• Travelling_salesman_problem type Attribute100024264.
• Travelling_salesman_problem type ComputationalProblemsInGraphTheory.
• Travelling_salesman_problem type Condition113920835.
• Travelling_salesman_problem type Course100038262.
• Travelling_salesman_problem type Difficulty114408086.
• Travelling_salesman_problem type Event100029378.
• Travelling_salesman_problem type GraphAlgorithms.
• Travelling_salesman_problem type HamiltonianPathsAndCycles.
• Travelling_salesman_problem type NP-completeProblems.
• Travelling_salesman_problem type Problem114410605.
• Travelling_salesman_problem type Procedure101023820.
• Travelling_salesman_problem type PsychologicalFeature100023100.
• Travelling_salesman_problem type Rule105846932.
• Travelling_salesman_problem type State100024720.
• Travelling_salesman_problem type Way100415676.
• Travelling_salesman_problem type YagoPermanentlyLocatedEntity.
• Travelling_salesman_problem comment "The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.TSP is a special case of the travelling purchaser problem.In the theory of computational complexity, the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems. ".
• Travelling_salesman_problem label "Handelsreizigersprobleem".
• Travelling_salesman_problem label "Problem des Handlungsreisenden".
• Travelling_salesman_problem label "Problem komiwojażera".
• Travelling_salesman_problem label "Problema del commesso viaggiatore".
• Travelling_salesman_problem label "Problema del viajante".
• Travelling_salesman_problem label "Problema do caixeiro-viajante".
• Travelling_salesman_problem label "Problème du voyageur de commerce".
• Travelling_salesman_problem label "Travelling salesman problem".
• Travelling_salesman_problem label "Задача коммивояжёра".
• Travelling_salesman_problem label "مسألة البائع المتجول".
• Travelling_salesman_problem label "巡回セールスマン問題".
• Travelling_salesman_problem label "旅行推销员问题".
• Travelling_salesman_problem sameAs Problém_obchodního_cestujícího.
• Travelling_salesman_problem sameAs Problem_des_Handlungsreisenden.
• Travelling_salesman_problem sameAs Problema_del_viajante.
• Travelling_salesman_problem sameAs Saltzaile_ibiltariaren_ebazkizun.
• Travelling_salesman_problem sameAs Problème_du_voyageur_de_commerce.
• Travelling_salesman_problem sameAs Problema_del_commesso_viaggiatore.
• Travelling_salesman_problem sameAs 巡回セールスマン問題.
• Travelling_salesman_problem sameAs 외판원_문제.
• Travelling_salesman_problem sameAs Handelsreizigersprobleem.
• Travelling_salesman_problem sameAs Problem_komiwojażera.
• Travelling_salesman_problem sameAs Problema_do_caixeiro-viajante.
• Travelling_salesman_problem sameAs m.07pbw.
• Travelling_salesman_problem sameAs Q322212.
• Travelling_salesman_problem sameAs Q322212.
• Travelling_salesman_problem sameAs Travelling_salesman_problem.
• Travelling_salesman_problem wasDerivedFrom Travelling_salesman_problem?oldid=606411437.
• Travelling_salesman_problem depiction William_Rowan_Hamilton_painting.jpg.
• Travelling_salesman_problem isPrimaryTopicOf Travelling_salesman_problem.