Local search is a powerful and widely used heuristic method (with various extensions). In this lecture we introduce this technique in the context of approximation algorithms. The basic outline of local search is as follows. For an instance $I$$I$II of a given problem let $\mathcal{S}(I)$$\mathcal{S}(I)$S(I)\mathcal{S}(I) denote the set of feasible solutions for $I$$I$II. For a solution $S$$S$SS we use the term (local) neighborhood of $S$$S$SS to be the set of all solutions $S^{\mathrm{\prime }}$$S^{\mathrm{\prime }}$S^(')S^{\prime} such that $S^{\mathrm{\prime }}$$S^{\mathrm{\prime }}$S^(')S^{\prime} can be obtained from $S$$S$SS via some local moves. We let $N(S)$$N(S)$N(S)N(S) denote the neighborhood of $S$$S$SS.

For minimization problems $S^{\mathrm{\prime }}$$S^{\mathrm{\prime }}$S^(')S^{\prime} is strictly better than $S$$S$SS if $\mathrm{val}\left(S^{\mathrm{\prime }}\right)<\mathrm{val}(S)$$\mathrm{val}\left(S^{\mathrm{\prime }}\right)<\mathrm{val}(S)$val(S^(')) < val(S)\operatorname{val}\left(S^{\prime}\right)<\operatorname{val}(S) whereas for maximization problems it is the case if $\mathrm{val}\left(S^{\mathrm{\prime }}\right)>\mathrm{val}(S)$$\mathrm{val}\left(S^{\mathrm{\prime }}\right)>\mathrm{val}(S)$val(S^(')) > val(S)\operatorname{val}\left(S^{\prime}\right)>\operatorname{val}(S).

The running time of the generic local search algorithm depends on several factors. First, we need an algorithm that given a solution $S$$S$SS either declares that $S$$S$SS is a local optimum or finds a solution $S^{\mathrm{\prime }}\in N(S)$$S^{\mathrm{\prime }}\in N(S)$S^(')in N(S)S^{\prime} \in N(S) such that $\mathrm{val}\left(S^{\mathrm{\prime }}\right)$$\mathrm{val}\left(S^{\mathrm{\prime }}\right)$val(S^('))\operatorname{val}\left(S^{\prime}\right) is strictly better than $\mathrm{val}(S)$$\mathrm{val}(S)$val(S)\operatorname{val}(S). A standard and easy approach for this is to ensure that the local moves are defined in such a way that $|N(S)|$$|N(S)|$|N(S)||N(S)| is polynomial in the input size $|I|$$|I|$|I||I| and $N(S)$$N(S)$N(S)N(S) can be enumerated efficiently; thus one can check each $S^{\mathrm{\prime }}\in N(S)$$S^{\mathrm{\prime }}\in N(S)$S^(')in N(S)S^{\prime} \in N(S) to see if any of them is an improvement over $S$$S$SS. However, in some more advanced settings, $N(S)$$N(S)$N(S)N(S) may be exponential in the input size but one may be able to find a solution in $S^{\mathrm{\prime }}\in N(S)$$S^{\mathrm{\prime }}\in N(S)$S^(')in N(S)S^{\prime} \in N(S) that improves on $S$$S$SS in polynomial time. Second, the running time of the algorithm depends also on the number of iterations it takes to go from $S_0$$S_0$S_(0)S_{0} to a local optimum. In the worst case the number of iterations could be $|\mathrm{OPT}-\mathrm{val}\left(S_0\right)|$$|\mathrm{OPT}-\mathrm{val}\left(S_0\right)|$|OPT-val(S_(0))||\operatorname{OPT} -\operatorname{val}\left(S_{0}\right)| which can be exponential in the input size. One can often use a standard scaling trick to overcome this issue; we stop the algorithm unless the improvement obtained over the current $S$$S$SS is a significant fraction of $\mathrm{val}(S)$$\mathrm{val}(S)$val(S)\operatorname{val}(S). Finally, the quality of the initial solution $S_0$$S_0$S_(0)S_{0} also factors into the running time.

Remark 8.1. There is a distinction made sometimes in the literature between oblivious and non-oblivious local search. In oblivious local search the algorithm uses $f$$f$ff as a black box when comparing $S$$S$SS with a candidate solution $S^{\mathrm{\prime }}$$S^{\mathrm{\prime }}$S^(')S^{\prime}; the analysis and the definition of local moves are typically based on properties of $f$$f$ff. In non-oblivious local search one may use an auxiliary function $g$$g$gg derived from $f$$f$ff in comparing $S$$S$SS with $S^{\mathrm{\prime }}$$S^{\mathrm{\prime }}$S^(')S^{\prime}. Typically the function $g$$g$gg is some kind of potential function that aids the analysis. This allows one to move to a solution $S^{\mathrm{\prime }}$$S^{\mathrm{\prime }}$S^(')S^{\prime} even though $f\left(S^{\mathrm{\prime }}\right)$$f\left(S^{\mathrm{\prime }}\right)$f(S^('))f\left(S^{\prime}\right) may not be an improvement over $f(S)$$f(S)$f(S)f(S).

Remark 8.2. There are several heuristics that are (loosely) connected to local search. These include simulated annealing, tabu search, genetic algorithms and others. These fall under the broad terminology of metaheuristics.

We illustrate local search for the well-known Max Cut problem. In Max Cut we are given an undirected graph $G=(V,E)$$G=(V,E)$G=(V,E)G=(V, E) and the goal is to partition $V$$V$VV into $(S,V\mathrm{\setminus }S)$$(S,V\mathrm{\setminus }S)$(S,V\\S)(S, V \backslash S) so as to maximize the number of edges crossing $S$$S$SS, that is, $|{\delta }_G(S)|$$\left|{\delta }_G(S)\right|$|delta_(G)(S)|\left|\delta_{G}(S)\right|; we will use $\delta (S)$$\delta (S)$delta(S)\delta(S) when $G$$G$GG is clear. For a vertex $v$$v$vv we use $\delta (v)$$\delta (v)$delta(v)\delta(v) instead of $\delta (\{v\})$$\delta (\{v\})$delta({v})\delta(\{v\}) to simplify notation. In the weighted version each edge $e$$e$ee has a non-negative weight $w(e)$$w(e)$w(e)w(e) the goal is to maximize the weight of the edges crossing $S$$S$SS, that is, $w(\delta (S))$$w(\delta (S))$w(delta(S))w(\delta(S)); here $w(A)$$w(A)$w(A)w(A) for a set $A$$A$AA denotes the quantity $\sum _{e\in A}w(e)$$\sum _{e\in A} w(e)$sum_(e in A)w(e)\sum_{e \in A} w(e).

We consider a simple local search algorithm for Max Cut that starts with an arbitrary set $S\subseteq V$$S\subseteq V$S sube VS \subseteq V and in each iteration either adds a vertex to $S$$S$SS or removes a vertex from $S$$S$SS as long as it improves the cut value $\delta (S)$$\delta (S)$delta(S)\delta(S).

We will first focus on the quality of solution output by the local search algorithm.

Lemma 8.1. Let $S$$S$SS be the output of the local search algorithm. Then for each vertex $v,w(\delta (S)\cap \delta (v))\ge w(\delta (v))/2$$v,w(\delta (S)\cap \delta (v))\ge w(\delta (v))/2$v,w(delta(S)nn delta(v)) >= w(delta(v))//2v, w(\delta(S) \cap \delta(v)) \geq w(\delta(v)) / 2.

Proof. Let ${\alpha }_v=w(\delta (S)\cap \delta (v))$${\alpha }_v=w(\delta (S)\cap \delta (v))$alpha_(v)=w(delta(S)nn delta(v))\alpha_{v}=w(\delta(S) \cap \delta(v)) be the weight of edges among those incident to $v$$v$vv that cross the cut $S$$S$SS. Let ${\beta }_v=w(\delta (v))-{\alpha }_v$${\beta }_v=w(\delta (v))-{\alpha }_v$beta_(v)=w(delta(v))-alpha_(v)\beta_{v}=w(\delta(v))-\alpha_{v}.

We claim that ${\alpha }_v\ge {\beta }_v$${\alpha }_v\ge {\beta }_v$alpha_(v) >= beta_(v)\alpha_{v} \geq \beta_{v} for each $v$$v$vv. If $v\in V\mathrm{\setminus }S$$v\in V\mathrm{\setminus }S$v in V\\Sv \in V \backslash S and ${\alpha }_v<{\beta }_v$${\alpha }_v<{\beta }_v$alpha_(v) < beta_(v)\alpha_{v}<\beta_{v} then moving $v$$v$vv to $S$$S$SS will strictly increase $w(\delta (S))$$w(\delta (S))$w(delta(S))w(\delta(S)) and $S$$S$SS cannot be a local optimum. Similarly if $v\in S$$v\in S$v in Sv \in S and ${\alpha }_v<{\beta }_v$${\alpha }_v<{\beta }_v$alpha_(v) < beta_(v)\alpha_{v}<\beta_{v}, we would have $w(\delta (S-v))>w(\delta (S))$$w(\delta (S-v))>w(\delta (S))$w(delta(S-v)) > w(delta(S))w(\delta(S-v))>w(\delta(S)) and $S$$S$SS would not be a local optimum.

Corollary 8.1. If $S$$S$SS is a local optimum then $w(\delta (S))\ge w(E)/2\ge \mathrm{OPT}/2$$w(\delta (S))\ge w(E)/2\ge \mathrm{OPT}/2$w(delta(S)) >= w(E)//2 >= OPT //2w(\delta(S)) \geq w(E) / 2 \geq \operatorname{OPT} / 2.

Proof. Since each edge is incident to exactly two vertices we have $w(\delta (S))=$$w(\delta (S))=$w(delta(S))=w(\delta(S))= $\frac{1}{2}\sum _{v\in V}w(\delta (S)\cap \delta (v))$$\frac{1}{2}\sum _{v\in V} w(\delta (S)\cap \delta (v))$(1)/(2)sum_(v in V)w(delta(S)nn delta(v))\frac{1}{2} \sum_{v \in V} w(\delta(S) \cap \delta(v)). Apply the above lemma,

since $\text{OPT}\le w(E)$$\text{OPT}\le w(E)$"OPT" <= w(E)\text{OPT} \leq w(E).

The running time of the local search algorithm depends on the number of local improvement iterations; checking whether there is a local move that results in an improvement can be done by trying all possible vertices. If the graph is unweighted then the algorithm terminates in at most $|E|$$|E|$|E||E| iterations. However, in the weighted case, it is known that the algorithm can take an exponential time in $|V|$$|V|$|V||V| when the weights are large. A very interesting problem is whether one can find a local optimum efficiently - note that we do not need to find a local optimum by doing local search! It is believed that finding a local optimum for Max Cut in the weighted case is hard. There is a complexity class called PLS that was defined by Johnson, Papadimitrioiu and Yannakakis for which Max Cut is known to be a complete problem. PLS plays an important role in algorithmic game theory in recent times. We refer the reader to the Wikipedia page on PLS for many pointers.

Many local search algorithms can be modified slightly to terminate with an approximate local optimum such that (i) the running time of the modified algorithm is strongly polynomial in the input size and (ii) the quality of the solution is very similar to that given by the original local search. We illustrate these ideas for Max Cut. Consider the following algorithm where $ϵ>0$$ϵ>0$epsilon > 0\epsilon>0 is a parameter that can be chosen. Let $n$$n$nn be the number of nodes in $G$$G$GG.

The above algorithm terminates unless the improvement is a relative factor of $(1+\frac{ϵ}{n})$$(1+\frac{ϵ}{n})$(1+(epsilon )/(n))(1+\frac{\epsilon}{n}) over the current solution's value. Thus the final output $S$$S$SS is an approximate local optimum.

Remark 8.3. An alert reader may wonder why the improvement is measured with respect to the global value $w(\delta (S))$$w(\delta (S))$w(delta(S))w(\delta(S)) rather than with respect to $w(\delta (v))$$w(\delta (v))$w(delta(v))w(\delta(v)). One reason is to illustrate the general idea when one may not have fine grained information about the function like we do here in the specific case of Max Cut. The global analysis will also play a role in the running time analysis as we will see shortly.

Lemma 8.2. Let $S$$S$SS be the output of the modified local search algorithm for Max Cut. Then $w(\delta (S))\ge \frac{1}{2(1+ϵ/4)}w(E)$$w(\delta (S))\ge \frac{1}{2(1+ϵ/4)}w(E)$w(delta(S)) >= (1)/(2(1+epsilon//4))w(E)w(\delta(S)) \geq \frac{1}{2(1+\epsilon / 4)} w(E).

Proof. As before let ${\alpha }_v=w(\delta (S)\cap \delta (v))$${\alpha }_v=w(\delta (S)\cap \delta (v))$alpha_(v)=w(delta(S)nn delta(v))\alpha_{v}=w(\delta(S) \cap \delta(v)) and ${\beta }_v=w(\delta (v))-{\alpha }_v$${\beta }_v=w(\delta (v))-{\alpha }_v$beta_(v)=w(delta(v))-alpha_(v)\beta_{v}=w(\delta(v))-\alpha_{v}. Since $S$$S$SS is an approximately local optimum we claim that for each $v$$v$vv

Otherwise a local move using $v$$v$vv would improve $S$$S$SS by more than $(1+ϵ/n)$$(1+ϵ/n)$(1+epsilon//n)(1+\epsilon / n) factor. (The formal proof is left as an exercise to the reader).

We have,

Therefore $w(S)(1+ϵ/4)\ge w(E)/2$$w(S)(1+ϵ/4)\ge w(E)/2$w(S)(1+epsilon//4) >= w(E)//2w(S)(1+\epsilon / 4) \geq w(E) / 2 and the lemma follows.

Now we argue about the number of iterations of the algorithm.

Lemma 8.3. The modified local search algorithm terminates in $O(\frac{1}{ϵ}n\log n)$$O(\frac{1}{ϵ}n\log n)$O((1)/(epsilon)n log n)O(\frac{1}{\epsilon} n \log n) iterations of the improvement step.

Proof. We observe that $w\left(S_0\right)=w\left(\delta \left(v^{\ast }\right)\right)\ge \frac{2}{n}w(E)$$w\left(S_0\right)=w\left(\delta \left(v^{\ast }\right)\right)\ge \frac{2}{n}w(E)$w(S_(0))=w(delta(v^(**))) >= (2)/(n)w(E)w\left(S_{0}\right)=w\left(\delta\left(v^{*}\right)\right) \geq \frac{2}{n} w(E) (why?). Each local improvement iteration improves $w(\delta (S))$$w(\delta (S))$w(delta(S))w(\delta(S)) by a multiplicative factor of $(1+ϵ/n)$$(1+ϵ/n)$(1+epsilon//n)(1+\epsilon / n). Therefore if $k$$k$kk is the number of iterations that the algorithm, then $(1+ϵ/n{)}^{k}w\left(S_0\right)\le w(\delta (S)$$(1+ϵ/n{)}^{k}w\left(S_0\right)\le w(\delta (S)$(1+epsilon//n)^(k)w(S_(0)) <= w(delta(S)(1+\epsilon / n)^{k} w\left(S_{0}\right) \leq w(\delta(S) where $S$$S$SS is the final output. However, $w(\delta (S))\le w(E)$$w(\delta (S))\le w(E)$w(delta(S)) <= w(E)w(\delta(S)) \leq w(E). Hence

which implies that $k=O(\frac{1}{ϵ}n\log n)$$k=O(\frac{1}{ϵ}n\log n)$k=O((1)/(epsilon)n log n)k=O(\frac{1}{\epsilon} n \log n).

A tight example for local optimum: Does the local search algorithm do better than $1/2$$1/2$1//21 / 2? Here we show that a local optimum is no better than a $1/2$$1/2$1//21 / 2-approximation. Consider a complete bipartite graph $K_{2n,2n}$$K_{2n,2n}$K_(2n,2n)K_{2 n, 2 n} with $2n$$2n$2n2 n vertices in each part. If $L$$L$LL and $R$$R$RR are the parts of a set $S$$S$SS where $|S\cap L|=n=|S\cap R|$$|S\cap L|=n=|S\cap R|$|S nn L|=n=|S nn R||S \cap L|=n=|S \cap R| is a local optimum with $|\delta (S)|=|E|/2$$|\delta (S)|=|E|/2$|delta(S)|=|E|//2|\delta(S)|=|E| / 2. The optimum solution for this instance is $|E|$$|E|$|E||E|.

Max Directed Cut: A problem related to Max Cut is Max Directed Cut in which we are given a directed edge-weighted graph $G=(V,E)$$G=(V,E)$G=(V,E)G=(V, E) and the goal is to find a set $S\subseteq V$$S\subseteq V$S sube VS \subseteq V that maximizes $w({\delta }_G^{+}(S))$$w\left({\delta }_G^{+}(S)\right)$w(delta_(G)^(+)(S))w\left(\delta_{G}^{+}(S)\right); that is, the weight of the directed edges leaving $S$$S$SS. One can apply a similar local search as the one for Max Cut. However, the following example shows that the output $S$$S$SS can be arbitrarily bad. Let $G=(V,E)$$G=(V,E)$G=(V,E)G=(V, E) be a directed in-star with center $v$$v$vv and arcs connecting each of $v_1,\dots ,v_n$$v_1,\dots ,v_n$v_(1),dots,v_(n)v_{1}, \ldots, v_{n} to $v$$v$vv. Then $S=\{v\}$$S=\{v\}$S={v}S=\{v\} is a local optimum with ${\delta }^{+}(S)=\mathrm{\varnothing }$${\delta }^{+}(S)=\mathrm{\varnothing }$delta^(+)(S)=O/\delta^{+}(S)=\emptyset while OPT $=n$$=n$=n=n. However, a minor tweak to the algorithm gives a $1/3$$1/3$1//31 / 3-approximation! Instead of returning the local optimum $S$$S$SS return the better of $S$$S$SS and $V\mathrm{\setminus }S$$V\mathrm{\setminus }S$V\\SV \backslash S. This step is needed because the directed cuts are not symmetric.

In this section we consider the utility of local search for maximizing nonnegative submodular functions. Let $f:2^V\to {\mathbb{R}}_{+}$$f:2^V\to {\mathbb{R}}_{+}$f:2^(V)rarrR_(+)f: 2^{V} \rightarrow \mathbb{R}_{+} be a non-negative submodular set function on a ground set $V$$V$VV. Recall that $f$$f$ff is submodular if $f(A)+f(B)\ge$$f(A)+f(B)\ge$f(A)+f(B) >=f(A)+f(B) \geq $f(A\cup B)+f(A\cap B)$$f(A\cup B)+f(A\cap B)$f(A uu B)+f(A nn B)f(A \cup B)+f(A \cap B) for all $A,B\subseteq V$$A,B\subseteq V$A,B sube VA, B \subseteq V. Equivalently $f$$f$ff is submodular if $f(A+v)-$$f(A+v)-$f(A+v)-f(A+v)- $f(A)\ge f(B+v)-f(B)$$f(A)\ge f(B+v)-f(B)$f(A) >= f(B+v)-f(B)f(A) \geq f(B+v)-f(B) for all $A\subset B$$A\subset B$A sub BA \subset B and $v\notin B$$v\notin B$v!in Bv \notin B. $f$$f$ff is monotone if $f(A)\le f(B)$$f(A)\le f(B)$f(A) <= f(B)f(A) \leq f(B) for all $A\subseteq B$$A\subseteq B$A sube BA \subseteq B. $f$$f$ff is symmetric if $f(A)=f(V\mathrm{\setminus }A)$$f(A)=f(V\mathrm{\setminus }A)$f(A)=f(V\\A)f(A)=f(V \backslash A) for all $A\subseteq V$$A\subseteq V$A sube VA \subseteq V. Submodular functions arise in a number of settings in combinatorial optimization. Two important examples are the following.