Local Search

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

• NP Completeness
• The 2SAT Problem

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.

Local Search Algorithms

• The Maximum Cut Problem
• Papadimitriou's 2SAT randomized local search algorithm