Local Search: Difference between revisions
Jump to navigation
Jump to search
Line 9: | Line 9: | ||
* Neighborhood. | * Neighborhood. | ||
* Generic local search algorithm. | * 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]] | ||
* [[The 2SAT Problem]] | * [[The 2SAT Problem]] |
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.