CS787: Advanced Algorithms
Scribe: Yiying Zhang and Baris Aydinlioglu Lecturer: Shuchi Chawla
Topic: Local Search Based Appoximation Date: October 03, 2007
Today we talk about an important technique of approximation algorithms: local search. We first
give fundamental ideas of local search approximation. Then we look into two problems where local
search based approximation algorithms apply, max-cut problem and facility location problem.
10.1 Fundamentals of Local Search
The basic idea of local search is to find a good local optima quickly enough to approximate the
global optima. This idea is somewhat like hill climbing. Starting from an arbitrary point, we try
to go down or climb up a little step and compare the objective value at the new point to that at
the old point. We then choose the step that increase the objective value. In this manner, we finally
reach a local maximal. Such algorithm is also known as ascending or descending algorithm.
We can also explain local search method using a graph. We consider a graph, whose nodes are
feasible solutions and whose edges connect two “neighboring” feasible solutions. Two feasible
solutions are neighbors if from either one we can obtain the other by a single “local” step. What
constitutes a local step depends on the problem, as we will see through examples later. Note that
we do not construct the entire graph, as its size would usually be exponential.
Once the structure of the graph is decided, in order to find a local optimum, we start with an
arbitrary node in the graph of feasible solutions, and we look at its neighbors to see if there is a
node with a better objective value. If there is, we find we move to that node feasible solution in
the graph. We don’t necessarily look for the neighboring node with the b est objective value; in
most cases a better value is enough. We repeat this process until there is no neighbor with a better
objective value. At that point we find the local optimum. See figure below.
Starting Node
Local Maximal
Figure 10.1.1: Graph Representation of Local Search
1
剩余7页未读，继续阅读
资源评论
glbupt2019-04-08逼近算法方面的好资料。清晰- DXD东2014-05-26补充一下算法知识面吧
