# Lin–Kernighan heuristic

> combinatorial algorithm

**Wikidata**: [Q2835802](https://www.wikidata.org/wiki/Q2835802)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/Lin–Kernighan_heuristic)  
**Source**: https://4ort.xyz/entity/linkernighan-heuristic

## Summary
The Lin–Kernighan heuristic is a combinatorial algorithm designed to find approximate solutions to the travelling salesperson problem. It is named after its creators Shen Lin and Brian Kernighan and may sometimes produce suboptimal results despite its effectiveness.

## Key Facts
- The Lin–Kernighan heuristic is a type of heuristic that may produce approximate, incorrect, or suboptimal results
- It is a combinatorial algorithm designed specifically for solving the travelling salesperson problem
- The algorithm is named after its creators Shen Lin and Brian Kernighan
- It has instances in multiple languages, including English and French versions on Wikipedia
- The algorithm has a sitelink count of 2 across different language editions
- It has a Microsoft Academic ID (now discontinued): 103888782
- Its Freebase ID is /m/027kvc5

## FAQs
### Q: What is the primary purpose of the Lin–Kernighan heuristic?
A: The Lin–Kernighan heuristic is primarily used to find approximate solutions to the travelling salesperson problem, a classic optimization problem in computer science.

### Q: Who created the Lin–Kernighan heuristic?
A: The Lin–Kernighan heuristic was created by Shen Lin and Brian Kernighan, which is why the algorithm bears their names.

### Q: Does the Lin–Kernighan heuristic always find the optimal solution?
A: No, as a type of heuristic, the Lin–Kernighan algorithm may sometimes fail or produce approximate, incorrect, or suboptimal results.

### Q: How does the Lin–Kernighan heuristic compare to exact algorithms for the travelling salesperson problem?
A: Unlike exact algorithms that guarantee optimal solutions but are computationally expensive, the Lin–Kernighan heuristic provides a more efficient approach by trading optimality for computational speed, especially for large problem instances.

## Why It Matters
The Lin–Kernighan heuristic is significant because it addresses one of the most well-known problems in computer science and operations research: the travelling salesperson problem (TSP). This NP-hard problem has practical applications in logistics, circuit board design, and DNA sequencing. By providing a relatively efficient method to find good (though not necessarily optimal) solutions, the Lin–Kernighan heuristic has enabled practical implementations where exact solutions would be computationally infeasible. Its development marked an important milestone in the field of approximation algorithms and combinatorial optimization, influencing subsequent heuristic approaches to complex computational problems. Despite being a heuristic that may sometimes produce suboptimal results, its widespread adoption demonstrates the practical trade-offs between solution quality and computational efficiency in real-world applications.

## Notable For
- Its specialization in solving the computationally difficult travelling salesperson problem
- Being named after its creators Shen Lin and Brian Kernighan
- Its classification as both a heuristic and a combinatorial algorithm, balancing approximation with systematic approaches
- Its practical applicability despite the theoretical possibility of suboptimal results

## Body
### Overview
The Lin–Kernighan heuristic is a combinatorial algorithm designed to solve the travelling salesperson problem (TSP). It falls into the category of heuristics, meaning it may sometimes fail or produce approximate, incorrect, or suboptimal results.

### Origins
The algorithm is named after its creators Shen Lin and Brian Kernighan. Their work has been influential in the field of optimization algorithms, though the exact creation date is not specified in the source material.

### Technical Classification
- Type: combinatorial algorithm
- Subclass: heuristic
- Problem domain: travelling salesperson problem

### Recognition
- Recognized in multiple Wikipedia language editions (English and French)
- Assigned Microsoft Academic ID: 103888782 (now discontinued)
- Listed in Freebase with ID: /m/027kvc5
- Has 2 sitelinks across different language editions

### Practical Application
The heuristic is primarily used for finding approximate solutions to the travelling salesperson problem, which involves finding the shortest possible route that visits a set of locations exactly once and returns to the origin. This has applications in logistics, routing, and optimization problems across various industries.

## References

1. [OpenAlex](https://docs.openalex.org/download-snapshot/snapshot-data-format)