Local Search: Difference between revisions
Jump to navigation
Jump to search
| (5 intermediate revisions 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: | |||
* Candidate solutions. | |||
* Neighborhood. | |||
* Generic local search algorithm. | |||
</font> | |||
In general, local search heuristics are not guaranteed to run in polynomial time, the [[Papadimitriou's 2SAT Algorithm#Overview|Papadimitriou's 2SAT randomized local search algorithm]] is one of those rare case when polynomial time correct convergence can be proven. | |||
=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 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.