Local Search: Difference between revisions
Jump to navigation
Jump to search
| Line 4: | Line 4: | ||
=Internal= | =Internal= | ||
* [[NP_Completeness#Subjects|NP Completeness]] | * [[NP_Completeness#Subjects|NP Completeness]] | ||
* [[The 2SAT Problem]] | |||
=Overview= | =Overview= | ||
<font color=darkkhaki>TODO: | <font color=darkkhaki>TODO: | ||
Revision as of 04:29, 30 November 2021
External
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/mT2vp/principles-of-local-search-i
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/gBJy8/principles-of-local-search-ii
Internal
Overview
TODO:
- Candidate solutions.
- Neighborhood.
- Generic local search algorithm.
In general, local search heuristics are not guaranteed to run in polynomial time, the Papadimitriou's 2SAT randomized local search algorithm is one of those rare case when polynomial time correct convergence can be proven.