Skip to content

12 Local Search

Intro#

  • Guess
  • Neighborhood
  • Global Minimum

Framework#

  • Local
    • 定义邻域
    • 局部最优解 local optimum
  • Search
    • 初始猜测解，search for a better one

Neighbor Relation#

  • 邻居解 \(S\sim S'\): \(S'\) is a neighboring solution of \(S-S'\) can be obtained by a samll modification of S.
  • 邻域 \(N(S)\): neighborhood of \(S-\{S':S\sim S'\}\)

Note

Greedy Algorithm 不是 Local Search 的一种特殊情况

Vertex Cover Problem#

  • 可行解 \(FS\): all vertex covers
  • cost = \(|S|\)
  • 梯度下降法：每次看看删除一个点是否可行，操作不可撤销

Metropolis Algorithm#

  • 如果新的 cost 更好，则更新
  • 如果新的 cost 更坏，则按照 \(e^{-\Delta \text{cost}/(kT)}\) 的概率更新
  • 如何执行和返回
    • 固定迭代 10000 次
    • 动态调整 \(T\) 的大小 模拟退火

补充：二分图上的顶点覆盖和匹配问题

  • 匹配问题：找到最大的边的子集，其中任意两边没有共同顶点
  • 柯尼希定理：二分图中的最大匹配边数等于最小顶点覆盖顶点数

Hopfield Neural Networks#

__assets/ADS 12 Local Search/IMG-ADS 12 Local Search-20241125150840662.webp

Intro#

  • 目标是找到一种足够好的布局 (configuration)
    • 如果一条边能使 \(w_{e}s_{u}s_{v}<0\)，则为 good，反之 bad
    • 如果一个顶点能满足 \(\sum_{v:e=(u,v)\in E}w_{e}s_{u}s_{v}\leq 0\)，也就是所有关联边的权重和 \(<=0\)，则称为满意点(satisfied)
    • 如果一张图所有点都是满意点，那么这个 configuration 是 stable 的

State-flipping Algorithm#

1
2
3
4
5
6
7
8
9
ConfigType State_flipping()
{
    Start from an arbitrary config S;
    while (!IsStable(S)) {
        u = GetUnsatisfied(S);
        state[u] = -state[u];
    }
    return S;
}

算法操作

  • 如果 unstable，找到 unsatisfied vertex 并翻转其状态，将其变为 satisfied
  • The state-flipping algorithm terminates at a stable config after at most \(W=\sum_{e}|w_{e}|\) 一定会在所有边权重和的绝对值次循环前停止
  • 通俗理解：一定会停止，因为每次的操作一定带来优化。

Maximum Cut#

最大化两个顶点集 \(A,B\) 之间所有边的权重和

2-approx#

  • 局部最优解能够达到 \(w(A,B)\geq \frac{1}{2}w(A^*,B^*)\)
  • 证明的关键在于子集内的距离和 \(2\sum_{\{u,n\}\subseteq A}w_{uv}<w(A,B)\)
  • 所以 2-approx

相关研究#

  • 存在一种 1.1382-approx 算法
  • 如果 \(\text{P}=\text{NP}\)，那么存在一种 \(\frac{17}{16}\)-approx 算法

终止策略#

  • 大提升翻转 (big-improvement-flip): 如果找不到一个能达到 \(\frac{2\varepsilon}{|V|}w(A,B)\) 提升的翻转，就终止
  • 终止的时候，满足 \((2+\varepsilon) w(A,B)\geq w(A^*,B^*)\)
  • 最多在 \(O(\frac{n}{\varepsilon}\log W)\) 后终止

更好的 local 定义？#

  • 解的邻域足够大，避免陷入局部最优
  • 也不能太大，否则效率更低
  • k-flip: 启发式算法，时间复杂度 \(\Theta(n^k)\)
    1. 第一步，对整个顶点集使用 state-flip
    2. 后面每一步，只对尚未 flip 过的顶点进行翻转
    3. 第 \(n\) 步，得到 \((A_{n},B_{n})=(A,B)\)

Discussion: Maximum Bipartite Matching#

Question

A bipartite graph \(G\) is one whose vertex set can be partitioned into two sets \(A\) and \(B\), such that each edge in the graph goes between a vertex in \(A\) and a vertex in \(B\). Matching \(M\) in \(G\) is a set of edges that have no end points in common. Maximum Bipartite Matching Problem finds a matching with the greatest number of edges (over all matchings).

Consider the following Gradient Ascent Algorithm:

As long as there is an edge whose endpoints are unmatched, add it to the current matching. When there is no longer such an edge, terminate with a locally optimal.

(a) Give an example of a bipartite graph \(G\) for which this gradient ascent algorithm does not return the maximum matching.

(b) Let \(M\) and \(M'\) be matchings in a bipartite graph \(G\). Suppose that \(|M'|>2|M|\). Show that there is an edge \(e'\) in \(M'\) such that (\(M \cup e'\)) is a matching in \(G\).

© Use (b) to conclude that any locally optimal matching returned by the gradient ascent algorithm in a bipartite graph \(G\) is at least half as large as a maximum matching in \(G\).

(a) Graph \(A-B-C-D\), which can be partitioned into \(\{A,C\}\) and \(\{B,D\}\). The optimal result is \(\{(A,B),(C,D)\}\), while if edge \((B,C)\) is added first, the algorithm does not return the maximum matching.

(b) \(2|M|\) vertices \(S_M\) are matched in \(M\), since \(|M'|>2|M|\), there exist an edge \(e'\) that are not incident with any vertex in \(S_M\). Then \(M \cup e'\) is a matching in \(G\).

© Suppose \(M^*\) is the maximum matching, \(M\) is the current solution generated by Gradient Ascent Algorithm. If \(|M|<\frac{1}{2}|M^*|\), by (b), there exists an \(e'\) that can be added to \(M\). Thus, the algorithm must return a \(M\) such that \(|M|\geq |M'|\).

Questions#

HW12#

FLP(Facility Location Problem) - center problem#

We are given a set of sites \(S = \{s_1, s_2, \cdots, s_n\}\) in the plane, and we want to choose a set of \(k\) centers \(C = \{c_1, c_2, \cdots, c_k\}\) so that the maximum distance from a site to the nearest center is minimized. Here \(c_i\) can be an arbitrary point in the plane.

A local search algorithm arbitrarily chooses \(k\) points in the plane to be the centers, then

  1. divide \(S\) into \(k\) sets, where \(S_i\) is the set of all sites for which \(c_i\) is the nearest center; and
  2. for each \(S_i\), compute the central position as a new center for all the sites in \(S_i\).

If steps (1) and (2) cause the covering radius to strictly decrease, we perform another iteration, otherwise the algorithm stops.

When the above local search algorithm terminates, the covering radius of its solution is at most 2 times the optimal covering radius. (T/F)

Answer

F，存在例外，参考 Homework - Jianjun Zhou's Notebook 可以构造无限差的情况，如果有四个点排成长方形，长边接近无限长，短边比较长，若 \(k=2\)，初始选择了长边的端点，那么近似比可以是无限大

Partition Problem#

There are \(n\) jobs, and each job \(j\) has a processing time \(t_j\)​. We will use a local search algorithm to partition the jobs into two groups \(A\) and \(B\), where set \(A\) is assigned to machine \(M_1\)​ and set \(B\) to \(M_2\)​. The time needed to process all of the jobs on the two machines is \(T_1​=\sum_{j\in A} ​t_j\)​, \(T_2​=\sum_{j \in B} ​t_j\)​. The problem is to minimize \(|T_1​−T_2​|\).

Local search: Start by assigning jobs \(1,\cdots,n/2\) to \(M_1\)​, and the rest to \(M_2\)​.
The local moves are to move a single job from one machine to the other, and we only move a job if the move decreases the absolute difference in the processing times. Which of the following statement is true?

A. The problem is NP-hard and the local search algorithm will not terminate. B. When there are many candidate jobs that can be moved to reduce the absolute difference, if we always move the job \(j\) with maximum \(t_j\)​, then the local search terminates in at most \(n\) moves. C. The local search algorithm always returns an optimal solution. D. The local search algorithm always returns a local solution with \(2/1​T_1​\le T_2​\le 2T_1\)​.

Answer

B A. 错误，由于进行操作一定会导致 cost 降低，一定会停止
B. 正确，之前移动的之后都不可能再次移动
C. 明显错误
D. 如果只有两个 job，就可以不对

SAT and N-Queen in approximation#

Local search algorithm can be used to solve lots of classic problems, such as SAT and \(N\)-Queen problems. Define the configuration of SAT to be \(X =\) vector of assignments of \(N\) boolean variables, and that of \(N\)-Queen to be \(Y =\) positions of the \(N\) queens in each column. The sizes of the search spaces of SAT and \(N\)-Queen are O(\(2^N\)) and O(\(N^N\)), respectively.

Answer

T，虽然 \(N\)-Queen 实际上不用搜索这么大的空间，但是表述成 \(O(N^N)\) 是没有任何问题的

Ex12#

判断题#

  1. For an optimization problem, given a neighborhood, if its local optimum is also a global optimum, one can reach an optimal solution with just one step of local improvements.
Answer

F，这里的 local improvement 指的是一个状态改变，但是 neighborhood 的步长可能大于 1

  1. Consider a state-flipping algorithm for the Maximum-Cut problem. We say that partitions (A,B) and (A′,B′) are neighbors under the k-flip rule if (A′,B′) can be obtained from (A,B) by moving at most k nodes from one side of the partition to the other. If (A,B) is a local optimum under the p-flip rule, it is also a local optimum under the k-flip rule for every k<p.
Answer

T，这里虽然可能最终得到的解不一样，但是对于第 \(k\) 次 flip 来说是一样的，因为第 \(k\) 次 flip 只关注一个状态

  1. Without any assumptions on the distances, if P \(\neq\) NP, there is no ρ-approximation for TSP (Travelling Salesman Problem) for any ρ≥1.
Answer

T，这里的 assumptions 指的是图论距离可能不满足现实的几何关系，例如不满足三角不等式。 如果没有这样的 assumptions，TSP 的近似算法可以任意差，例如构建非常长的一条边 但如果满足了三角不等式，那么存在很多种 \(\rho\)-approx 算法，例如 Christofides 算法就是 1.5-approx 的.

Minimum Degree Spanning Tree#

__assets/ADS 12 Local Search/IMG-ADS 12 Local Search-20241223103933667.webp

Answer

D A 显然错误，无环图的 degree 总和是 \(2|V|-2\) B 也有问题，进行一次操作后，删除的边 \(-(\geq d(w))\)，但是增加了一条 \(d(u)+1\) 的边（假设 \(d(u)>d(v)\)），并且还有两条边可能 \(+2\)，无法保证递减 C 有问题，对于操作中的 \(u,v,w\) 是满足的，实现了 \(-1\)，但是可能导致其他很多点对的值变大 D 正确，进行一次操作，考虑 \(w\) 减少 \(-(\geq 2 \cdot 3^{d(w)-1})\)，考虑 \(u,v\) 增加 \((2\cdot 3^{d(u)}+2\cdot 3^{d(v)})\)。假设 \(d(u)\geq d(v)\)，存在 \(d(w)-1\geq d(u)+1\)，所以整体递减，满足题意

Load Balancing Problem#

__assets/ADS 12 Local Search/IMG-ADS 12 Local Search-20241223103954502.webp

Answer
  1. 显然正确
  2. 显然正确，因为如果是两台机器，就变成了 partition 问题
  3. 不正确，对于 makespan 问题，如果有 \(m\) 台机器，简单贪心可以达到 \(2-\frac{1}{m}\) 的近似比
  4. 显然正确

Facility Location Problem#

__assets/ADS 12 Local Search/IMG-ADS 12 Local Search-20241223104337745.webp

Answer

Q13#

Since finding a locally optimal solution is presumably easier than finding an optimal solution, we can claim that for any local search algorithm, one step of searching in neighborhoods can always be done in polynomial time.

Answer

F，显然有些 local search 在 neighbor 空间里的搜索也可以是指数级的（例如 TSP 的一些局部 permute 搜索）

关键在于不能和 divide and conquer 中的假设子问题的时间复杂度为常数搞混了

Comments