Local Search: Difference between revisions
Jump to navigation
Jump to search
(One intermediate revision by the same user not shown) | |||
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: | ||
Line 15: | Line 17: | ||
=Local Search Algorithms= | =Local Search Algorithms= | ||
* [[The Maximum Cut Problem#Overview|The Maximum Cut Problem]] | * [[The Maximum Cut Problem#Overview|The Maximum Cut Problem]] | ||
* [[Papadimitriou's 2SAT Algorithm#Overview| | * [[Papadimitriou's 2SAT Algorithm#Overview|Papadimitriou's 2SAT randomized local search algorithm]] |
Latest 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.