About: Lin–Kernighan heuristic

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Lin–Kernighan heuristic Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Rule105846932, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/c/5WV45cQj7C

In combinatorial optimization, Lin–Kernighan is one of the best heuristics for solving the symmetric travelling salesman problem. It belongs to the class of local search algorithms, which take a tour (Hamiltonian cycle) as part of the input and attempt to improve it by searching in the neighbourhood of the given tour for one that is shorter, and upon finding one repeats the process from that new one, until encountering a local minimum. As in the case of the related 2-opt and 3-opt algorithms, the relevant measure of "distance" between two tours is the number of edges which are in one but not the other; new tours are built by reassembling pieces of the old tour in a different order, sometimes changing the direction in which a sub-tour is traversed. Lin–Kernighan is adaptive and has no fixed

Attributes	Values
rdf:type	yago:WikicatCombinatorialAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Heuristic105847956 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:WikicatHeuristicAlgorithms yago:WikicatHeuristics yago:YagoPermanentlyLocatedEntity yago:Rule105846932
rdfs:label	Lin–Kernighan heuristic (en) Heuristique de Lin-Kernighan (fr)
rdfs:comment	En optimisation combinatoire, l'heuristique de Lin-Kernighan est une heuristique pour le problème du voyageur de commerce. L'algorithme consiste à échanger itérativement un certain nombre d'arêtes à partir d'une solution donnée pour trouver une solution de meilleur coût. (fr) In combinatorial optimization, Lin–Kernighan is one of the best heuristics for solving the symmetric travelling salesman problem. It belongs to the class of local search algorithms, which take a tour (Hamiltonian cycle) as part of the input and attempt to improve it by searching in the neighbourhood of the given tour for one that is shorter, and upon finding one repeats the process from that new one, until encountering a local minimum. As in the case of the related 2-opt and 3-opt algorithms, the relevant measure of "distance" between two tours is the number of edges which are in one but not the other; new tours are built by reassembling pieces of the old tour in a different order, sometimes changing the direction in which a sub-tour is traversed. Lin–Kernighan is adaptive and has no fixed (en)
dct:subject	Combinatorial optimization Combinatorial algorithms Heuristic algorithms Travelling salesman problem
Wikipage page ID	8818888 (xsd:integer)
Wikipage revision ID	1096326698 (xsd:integer)
Link from a Wikipage to another Wikipage	Regular graph Combinatorial optimization Combinatorial optimization Combinatorial algorithms Trail (graph theory) Travelling salesman problem Local search (optimization) 3-opt Edge (graph theory) Eulerian path Factor (graph theory) 2-opt Heuristic algorithms Travelling salesman problem Symmetric difference Hamiltonian cycle Heuristic algorithm
Link from a Wikipage to an external page	http://www.research.att.com/~dsj/papers/TSPchapter.pdf%7Cchapter=The http://akira.ruc.dk/~keld/research/LKH-3/ https://github.com/kikocastroneto/lk_heuristic http://www.math.uwaterloo.ca/tsp/concorde.html
sameAs	Lin–Kernighan heuristic Lin–Kernighan heuristic Lin–Kernighan heuristic Lin–Kernighan heuristic
dbp:wikiPageUsesTemplate	dbt:About dbt:Citation_needed dbt:Cite_book dbt:Cite_journal dbt:Reflist
has abstract	In combinatorial optimization, Lin–Kernighan is one of the best heuristics for solving the symmetric travelling salesman problem. It belongs to the class of local search algorithms, which take a tour (Hamiltonian cycle) as part of the input and attempt to improve it by searching in the neighbourhood of the given tour for one that is shorter, and upon finding one repeats the process from that new one, until encountering a local minimum. As in the case of the related 2-opt and 3-opt algorithms, the relevant measure of "distance" between two tours is the number of edges which are in one but not the other; new tours are built by reassembling pieces of the old tour in a different order, sometimes changing the direction in which a sub-tour is traversed. Lin–Kernighan is adaptive and has no fixed number of edges to replace at a step, but favours small numbers such as 2 or 3. (en) En optimisation combinatoire, l'heuristique de Lin-Kernighan est une heuristique pour le problème du voyageur de commerce. L'algorithme consiste à échanger itérativement un certain nombre d'arêtes à partir d'une solution donnée pour trouver une solution de meilleur coût. (fr)
prov:wasDerivedFrom	wikipedia-en:Lin–Kernighan_heuristic?oldid=1096326698&ns=0
page length (characters) of wiki page	18774 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Lin–Kernighan_heuristic
is Link from a Wikipage to another Wikipage of	Brian Kernighan Travelling salesman problem 3-opt 2-opt Lin-Kernighan heuristic Lin-Kernighan Lin-Kernighan algorithm Lin–Kernighan Lin–Kernighan algorithm
is Wikipage redirect of	Lin-Kernighan heuristic Lin-Kernighan Lin-Kernighan algorithm Lin–Kernighan Lin–Kernighan algorithm
is known for of	Brian Kernighan
is foaf:primaryTopic of	wikipedia-en:Lin–Kernighan_heuristic

Faceted Search & Find service v1.17_git147 as of Sep 06 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3331 as of Sep 2 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 52 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software