Greedy and local search

1 set cover

Set Cover Problem

输入: 给定$m$个集合$S_1,S_2,\cdots,S_m\subseteq U$, $|U|=n$;
输出: 最小的$C\subseteq \{1,2,\cdots,m\}$, 满足$U=\cup_{i\in C}S_i$.
可以看做一个二部图. 如果把二部图左右反转, 得到等价的问题:

Hitting Set Problem

输入: 同上;
输出: 最小的$C\subseteq U$, 满足$C$和每一个集合$S_i$($1\le i\le n$)相交.

1.1 Frequency and Vertex Cover

对于一个set cover问题, 定义频率: $frequency(x)=|\{i|x\in S_i\}|$(一个元素连着几个集合).
当频率为2时, 即点覆盖问题(每条边连着2个点, 找最少的点把每条边都覆盖)

1.2 贪心算法

GreedyCover

输入: 集合$S_1,S_2,\cdots,S_m$;
算法:
initially, $U=\cup_{i=1}^mS_i$, $C=\emptyset$;
while $U\ne \emptyset$ do
$\qquad$find $i\in\{1,2,\cdots,m\}$ with the largest $|S_i\cap U|$;
$\qquad$Set $price(e)=\frac{1}{|S_i\cap U|}$ for all $e\in S_i\cap U$.
$\qquad$let $C=C\cup \{i\}$, and $U=U/S_i$;
return $C$;
近似分析:

$|C|=\sum_{e\in U}price(e)$;
对于第一个覆盖的元素$x_1$, $price(x_1)=\frac{1}{\max_i|S_i|}\le \frac{OPT(I)}{n}$
对于第k个覆盖的元素$x_k$, 此时未覆盖的元素的集合为$U_k$, 则$|U_k|= n-k+1$, 所以 $price(x_k)=\frac{1}{\max_i|S_i\cap U_t|}\le \frac{OPT(I_t)}{|U_t|}\le \frac{OPT(I)}{|U_t|}=\frac{OPT}{n-k+1}$
因此 $|C|=\sum_{e\in U}price(e)\le \sum_{k=1}^n\frac{OPT(I)}{n-k+1}=H_n\cdot OPT(I)$ 其中$H_n\approx \ln n+O(1)$为调和级数.

1.3 Prime-Dual算法

构造对偶问题:
Instance: $S_1,S_2,\cdots,S_m\subseteq U$.
Primal: 找到$C\subseteq [m]$满足$U_{i\in C}S_i=U$, 最小化$|C|$.
Dual: 找到$M\subseteq U$满足对于任意$i\in[m]$, $|S_i\cap M|\le 1$, 最大化$|M|$.(二部图的最大匹配)

弱对偶性:

$M$中的任意两个元素都不能被同一个$S_i$覆盖, 所以$M$中的每一个元素至少需要一个不同的$S_i$来覆盖, 也就是对于任何集合覆盖, 至少要$M$个集合来覆盖$M$中的所有元素, 也就是

$\forall C, \forall M: |M|\le |C|$

所以$\forall M:|M|\le OPT_{primal}=\min |C|$

DualCover

找到一个任意的极大匹配$M$, 返回$C=\{i:S_i\cap M=\emptyset\}$.
其中构造极大匹配的方法是: 不断加点进$M$直到不能加. 多项式时间.
$C$是集合覆盖的原因:

反证法: 假设$C$不是覆盖, 那么存在$x\in U$, 对于所有$i\in C$, $x\not\in S_i$, 说明$x\in M$, 而且也是匹配,则$M$加上$x$后也是匹配, $x$ 和$M$是最大匹配矛盾.

近似比:

$|C|\le \sum_{x\in M}frequency(x)\le f\cdot|M|\le f\cdot OPT$

其中, $f=\max_{x\in U}frequency(x)$为所有元素中的最大频率. 因此近似比为$f$.

点覆盖问题:

点覆盖问题为$f=2$的集合覆盖问题.
近似算法为:

当边集非空时
- 任意选择边$uv\in E$
- $u$和$v$都加入$C$
- 在$E$中去掉所有和$u$, $v$相邻的边.
  这是一个2-近似算法.

2 Scheduling

详细地见之前的近似算法博客和讲义. 下面较为简略.
问题:

$n$任务
$m$相同机器, 每个机器可以从$t=0$开始工作, 同时做至多一个任务
每个作业有需要的处理时间$p_j$.
找到一个工作分配方案, 最小化最后一个任务完成的时间.
$m=2$即为Partition问题, 所以是NPC问题.

2.1 Graham’s List algorithm

算法: 依次分配到最早完成当前所有任务的机器上.
近似比: $2-\frac{1}{m}$.
原因:

$OPT\ge \max_{1\le j\le n}p_j$
$OPT\ge \frac{1}{m}\sum_{j=1}^np_j$
最后完成的那个机器时间分成两部分:
- 前一部分小于等于除了最后一个任务以外所有任务总时长/m
- 后一部分为最后一个任务的时间$p_l$ $C_{max}\le \frac{1}{m}(\sum_{j=1}^np_j-p_l)+p_l\le (2-1/m)\cdot OPT$

2.2 Local search

算法: 先随便找一个分配方案, 之后不断将最后一个结束的任务转移到别的机器, 使得这个任务的完成时间更早, 直到无法进行这样的转移.
分析: 和上面的完全一样

2.3 Longest Processing Time

算法: 先将所有任务根据需要时间从长到短排序, 再执行Graham’s List algorithm.
近似比: $4/3$. (很好证明是$3/2$)

2.4 Online Algorithms and Competitive Ratio

Graham’s List algorithm实际上还是在线的. (每见到一个输入, 做一次决定, 而不需要见到所有输入之后再做决定.)(LPT就不是)
在线算法中, 引入了类似近似比的概念competitive ratio, $\alpha$-competitive表示$SOL\le \alpha OPT_I$, 其中SOL是在线算法的结果, 而$OPT_I$是最优离线算法的结果. Graham’s List algorithm就是$(2-1/m)$-competitive的.