Approximation Algorithms 近似算法

1.理解为什么会有近似算法，什么是近似算法，如何评价近似算法的优劣

2.掌握负载均衡问题的近似算法及其近似比证明；

3.掌握带权重的顶点覆盖问题的定价算法（Pricing method），证明该方法能得到一个2倍近似解；

4.理解带权重的顶点覆盖问题的整数规划模型如何建立的，理解松弛求解方法；

5.能够对一个图问题建立整数规划模型（例如：带权重的顶点覆盖问题，广义负载均衡问题）；

6.理解求解0-1背包问题的基于取整法的近似算法；

7.能够设计简单的近似算法，并证明该算法是几倍近似算法，典型考题：第5章课件P41练习题。

★Approximation Algorithms 近似算法

Coping with NP-completeness 应对NPC问题

Q. Suppose I need to solve an NP-complete problem. What should I do?
问：如何需要解决一个NP完全问题？

A. Sacrifice one of three desired features.
答：牺牲三个目标之一

i. Solve arbitrary instances of the problem.
求解问题的任意实例
ii. Solve problem to optimality.
得到最优解
iii. Solve problem in polynomial time.
在多项式时间内求解

Coping strategies.
应对策略

i. Design algorithms for special cases of the problem.
为问题的特殊情况设计算法
例如：难以解决四着色问题，可以解决平面图四着色问题
ii. Design approximation algorithms or heuristics.
设计近似算法或启发式算法
iii. Design algorithms that may take exponential time.
设计可能需要指数时间的算法

ρ-approximation algorithm ρ近似算法

Runs in polynomial time.
在多项式时间内运行
Applies to arbitrary instances of the problem.
适用于问题的任意实例
Guaranteed to find a solution within ratio ρ of true optimum.
在最优解的ρ比例内找到解

Ex. Given a graph G, can find a vertex cover that uses ≤ 2 OPT(G) vertices in O(m + n) time.
例如：给定图G，可以在O(m+n)时间内找到一个顶点覆盖，使用的顶点数小于等于最优解中使用的顶点数的2倍。

Challenge. Need to prove a solution’s value is close to optimum value, without even knowing what optimum value is!
挑战：在不知道最优解是什么的情况下，需要证明一个解的值接近最优解的值。

ρ近似比越接近1越好。

问题 > Approximation algorithms: vertex cover 顶点覆盖的近似算法

Vertex cover 顶点覆盖

VERTEX-COVER. Given a graph G = (V, E), find a min-size vertex cover.
顶点覆盖问题（最优化问题）：给定图G = (V, E)，找到一个最小的顶点覆盖

Greedy algorithm 顶点覆盖的贪心算法

Repeatedly pick an arbitrary edge (u, v).
不断选择任意边(u, v)

Add (u, v) to matching M.
将边(u, v)加入匹配集M
Add both u and v to vertex cover S.
将点u和v加入顶点覆盖S
Delete all edges incident to either u or v.
删除与u或v连接的所有边

Running time. Can be implemented in O(m + n) time.
运行时间：O(m + n)

最多可能运行n/2次（每次删除两个顶点）
最多可能运行m次（每次删除一条边）

Greedy algorithm is a 2-approximation algorithm 顶点覆盖的贪心算法是一个2倍近似算法

Theorem. Let S* be a minimum vertex cover. Then, greedy algorithm computes a vertex cover S with |S| ≤ 2 |S*|. (2-approximation algorithm)
定理：S*是一个最小的顶点覆盖，S是贪心算法计算的顶点覆盖，S中的顶点数≤2倍S*中的顶点数（2倍近似算法）

Pf. 证明：

S is a vertex cover. (delete edge only after it’s already covered)
S是一个顶点覆盖（只有当边被覆盖时才会被删除）
M is a matching. (when (u, v) added to M, all edges incident to either u or v are deleted)
M是一个匹配集（M中边只会连接两个不重复的顶点，没有公共顶点）（当边(u, v)加入M时，删除所有连接的所有边）
|S | = 2 |M | ≤ 2 |S*|.
S中顶点数=2倍M中边数（design. 根据算法设计：S中每加入2个顶点，M中加入1条边）
M中边数小于等于S*中顶点数（weak duality. 根据弱对偶：M中边只会连接两个不重复的顶点，没有公共顶点；定点覆盖要覆盖这条边，至少要包含两个顶点之一）

推论：匹配集的贪心算法是一个1/2近似算法

Corollary. Let M* be a maximum matching. Then, greedy algorithm computes a matching M with |M| ≥ ½ |M*|.
推论：M*是一个最大匹配集，M是贪心算法计算的匹配集，M中的边数≥1/2 M*中的边数（1/2近似算法）

Pf. |M| = ½ |S| ≥ ½ |M*|.
证明：S中顶点数≥M*边数（weak duality. 根据弱对偶：定点覆盖S要覆盖M*的一条边，至少要包含两个顶点之一）

Vertex cover inapproximability 顶点覆盖的不可逼近性

Theorem. [Dinur–Safra 2004] If P ≠ NP, then no ρ-approximation for VERTEX-COVER for any ρ < 1.3606.
定理：如果P ≠ NP，那么对于任意ρ < 1.3606，没有顶点覆盖的ρ近似算法

★问题 > Load balancing 负载均衡

m负载均衡问题

Input 输入

Input. m identical machines; n jobs, job j has processing time t_j.
输入：m台相同的机器；n个作业，任务j的处理时间为t_j。

Job j must run contiguously on one machine.
作业j必须在一台机器上连续运行
A machine can process at most one job at a time.
一台机器一次最多只能处理一个作业

Def. Load of machine 定义：负载

Def. Let S[i] be the subset of jobs assigned to machine i.
定义：设S[i]是分配给机器i的作业的子集。

The load of machine i is L[i] = Σ_j∈S[i] t_j.
i机器的负载L[i]是S[i]中作业的处理时间之和。

Def. Makespan 定义：制造时间

Def. The makespan is the maximum load on any machine L = max_i L[i].
制造时间L是任何机器上的最大负载

Load balancing 负载均衡问题

Assign each job to a machine to minimize makespan.
将作业分配给机器，使制造时间最小

2负载均衡问题

Load balancing on 2 machines is NP-hard 2负载均衡问题是NP难问题

Claim. Load balancing is hard even if m = 2 machines.

Pf. PARTITION ≤_P LOAD-BALANCE.
证明：划分问题归约到 2负载均衡问题

对于任意划分问题的实例，构造2负载均衡问题的实例：划分问题中每个数对应负载均衡问题的一个活动时长，要求的最小制造时间为所有活动时长之和的一半（要求平分所有活动）

List-scheduling algorithm 列表调度算法

Consider n jobs in some fixed order.
n个作业按某种固定顺序
Assign job j to machine i whose load is smallest so far.
每次将作业j分给目前最小负载的机器i

Implementation. O(n log m) using a priority queue for loads L[k].
执行：O(n log m) 使用优先级队列记录每台机器的负载L[k]

List scheduling analysis 列表调度算法分析：列表调度算法是2倍近似算法

Theorem. [Graham 1966] Greedy algorithm is a 2-approximation.
定理：列表调度算法是2倍近似算法

First worst-case analysis of an approximation algorithm.
首先对近似算法的最坏情况分析
Need to compare resulting solution with optimal makespan L*.
需要将生成解与最优解的制造时间L*进行比较。

Lemma 1. The optimal makespan L* ≥ max_j t_j.
引理1：最优解的制造时间L*大于等于最长作业的处理时间

Pf. Some machine must process the most time-consuming job.
证明：一定要有个机器处理耗时最长的任务

Lemma 2. The optimal makespan $L∗≥1m∑jtjL^*≥\frac{1}{m}\sum_{j}{t_j}$
引理2：最优解的制造时间L*大于等于所有作业处理时长之和/m

Pf. 证明

The total processing time is Σ_j t_j .
总处理时长等于所有作业处理时长之和
One of m machines must do at least a 1 / m fraction of total work.
至少有一个机器做多于或等于总工作量的 1/m

Theorem. [Graham 1966] Greedy algorithm is a 2-approximation.
定理：列表调度算法是2倍近似算法

Pf. Consider load L[i] of bottleneck machine i. (machine that ends up with highest load)
证明：设机器i负载L[i]最高（瓶颈机器）

Let j be last job scheduled on machine i.
作业j是机器i的最后一个作业
When job j assigned to machine i, i had smallest load. Its load before assignment is L[i] – t_j ⇒ L[i] – t_j ≤ L[k] for all 1 ≤ k ≤ m.
当作业j分配给机器i之前，机器i拥有最小的负载L[i] – t_j，所以减去作业j后，机器i的负载会小于任何机器的负载
Sum inequalities over all k and divide by m:
对于所有k的取值，将不等式求和，然后除以m，得到减去作业j后，机器i的负载会小于最优解
现在证明L≤2L*：加回作业j后，机器i的负载会小于最优解的2倍

列表调度算法是紧2倍近似算法

Q. Is our analysis tight?
A. Essentially yes.

例如：

列表调度算法的解

最优解

LPT rule 最长处理时间优先规则

Longest processing time (LPT). Sort n jobs in decreasing order of processing times; then run list scheduling algorithm.
最长处理时间优先规则：将作业按照最长处理时间优先排序，然后运行列表调度算法

最长处理时间优先规则是3/2倍近似算法

Observation. If bottleneck machine i has only 1 job, then optimal.
观察：如果瓶颈机器i只有一个作业，那么将是最优解

Pf. Any solution must schedule that job.
证明：任何最优解都必须这么安排这个作业，否则制造时间会比这长，就不是最优解了

Lemma 3. If there are more than m jobs, L* ≥ 2 t_m+1 .
引理3：如果有多于机器数量m多个作业，最优解会大于2倍第m+1个作业的处理时长

Pf. 证明

Consider processing times of first m+1 jobs t₁ ≥ t₂ ≥ … ≥ t_m+1.
前m+1个作业的处理时间递减
Each takes at least t_m+1 time.
每个至少花费t_m+1时间
There are m + 1 jobs and m machines, so by pigeonhole principle, at least one machine gets two jobs.
有m+1个作业和m台机器，根据鸽巢原理，至少一台机器可以得到两个作业，这台机器至少消耗2 t_m+1时间，所以最优解至少是2 t_m+1

Theorem. LPT rule is a 3/2-approximation algorithm.
定理：使用最长处理时间优先规则的列表调度算法是一个3/2倍近似算法

Pf. [ similar to proof for list scheduling ]
证明：和列表调度算法类似

Consider load L[i] of bottleneck machine i.
考虑瓶颈机器i的负载L[i]
Let j be last job scheduled on machine i. (assuming machine i has at least 2 jobs, we have j > m)
作业j是机器i的最后一个作业（假设机器i至少有2个作业，j > m），作业j至多消耗t_m+1，t_m+1 ≤ ½ L*，所以作业j之多消耗½ L*

最长处理时间优先规则是紧4/3倍近似算法

Q. Is our 3/2 analysis tight?
A. No.

Theorem. [Graham 1969] LPT rule is a 4/3-approximation.
Pf. More sophisticated analysis of same algorithm.
证明：对同一算法进行更加复杂的分析

Q. Is Graham’s 4/3 analysis tight?
A. Essentially yes.

Ex. 例如：

m machines
n = 2m + 1 jobs
2 jobs of length m, m + 1, …, 2m – 1 and one more job of length m.
Then, L / L* = (4m − 1) / (3m)

可行集的近似算法

问题 > Center selection 中心点选择

Center selection problem 中心点选择问题

Input. Set of n sites s₁, …, s_n and an integer k > 0.
输入：n个地点和正整数k

Center selection problem. Select set of k centers C so that maximum distance r(C) from a site to nearest center is minimized.
中心点选择问题：选择k个中心点C，所有地点中离最近中心点最远的距离为r(C)，要求r(C)最短

Notation. 符号说明

dist(x, y) = distance between sites x and y.
dist(x, y)：地点间的距离
dist(s_i, C) = min c ∈ C dist(s_i, c) = distance from s_i to closest center.
dist(s_i, C)：地点和最近中心点之间的距离
r(C) = max_i dist(s_i, C) = smallest covering radius.
r(C)：最大的地点和最近中心点之间的距离

Goal. Find set of centers C that minimizes r(C), subject to |C| = k.
找到一组中心点C，使r(C)最小

Distance function properties.
距离函数的特性

dist(x, x) = 0 [ identity ]
dist(x, y) = dist(y, x) [ symmetry ]
dist(x, y) ≤ dist(x, z) + dist(z, y) [ triangle inequality ]

Ex: each site is a point in the plane, a center can be any point in the plane, dist(x, y) = Euclidean distance.
每个点都是平面中的一个点，中心点可以是平面中任何点，dist(x, y)=欧几里德距离。

Remark: search can be infinite!
备注：搜索是无穷的

A false start 错误的尝试

Greedy algorithm. Put the first center at the best possible location for a single center, and then keep adding centers so as to reduce the covering radius each time by as much as possible.
贪心算法：假设只有一个中心点，将第一个中心点放在最有可能的位置；然后继续添加中心点，每次尽可能多的减少覆盖半径

Remark: arbitrarily bad!
评论：任意坏

Greedy algorithm 贪心算法

Repeatedly choose next center to be site farthest from any existing center.
反复选择离现有中心最远的站点作为下一个中心。

Property. Upon termination, all centers in C are pairwise at least r(C) apart.
特征：结束时，所有C中的中心点两两之间至少相距r(C)

Pf. By construction of algorithm.
证明：通过算法的构造

？？？

Greedy algorithm is a 2-approximation 贪心算法是一个2倍近似算法

Lemma. Let C* be an optimal set of centers. Then r(C) ≤ 2r(C*).
引理：贪心算法解不超过最优解的2倍

Pf. [by contradiction] Assume r(C*) < ½ r(C).
证明：反证法，假设最优解小于贪心解的½

For each site c_i ∈ C, consider ball of radius ½ r(C) around it.
Exactly one c_i* in each ball; let c_i be the site paired with c_i*.
Consider any site s and its closest center c_i* ∈ C*.
dist(s, C) ≤ dist(s, c_i) ≤ dist(s, c_i*) + dist(c_i*, c_i) ≤ 2r(C*).
(Δ-inequality)
(dist(s, c_i*) ≤ r(C*), dist(c_i*, c_i) ≤ r(C*) since c_i* is closest center)
Thus, r(C) ≤ 2r(C*).

Theorem. Greedy algorithm is a 2-approximation for center selection problem.
定理：贪心算法是一个2倍近似算法

Remark. Greedy algorithm always places centers at sites, but is still within a factor of 2 of best solution that is allowed to place centers anywhere. (e.g., points in the plane)
评论：贪心算法总是将中心点放置在站点上，但最大距离仍不超过最优解的2倍，最优解是允许将中心点放在任意位置（比如平面中的点）

Question. Is there hope of a 3/2-approximation? 4/3?

Dominating set reduces to center selection 支配集问题归约到中心点选择问题

Theorem. Unless P = NP, there no ρ-approximation for center selection problem for any ρ < 2.
定理：除非P = NP，否则不存在ρ < 2的中心点选择问题的ρ倍近似算法

Pf. We show how we could use a (2 – ε) approximation algorithm for CENTER-SELECTION selection to solve DOMINATING-SET in poly-time.

Let G = (V, E), k be an instance of DOMINATING-SET.
Construct instance Gʹ of CENTER-SELECTION with sites V and distances
- dist(u, v) = 1 if (u, v) ∈ E
- dist(u, v) = 2 if (u, v) ∉ E
Note that Gʹ satisfies the triangle inequality.
G has dominating set of size k iff there exists k centers C* with r(C*) = 1.
Thus, if G has a dominating set of size k, a (2 – ε)-approximation algorithm for CENTER-SELECTION would find a solution C* with r(C*) = 1 since it cannot use any edge of distance 2.

★问题 > Weighted vertex cover 带权顶点覆盖

Weighted vertex cover 带权顶点覆盖问题

Definition. Given a graph G = (V, E), a vertex cover is a set S ⊆ V such that each edge in E has at least one end in S.
定义：顶点覆盖中顶点要覆盖所有边

Weighted vertex cover. Given a graph G with vertex weights, find a vertex cover of minimum weight.
带权顶点覆盖问题：要求顶点覆盖中顶点的权值和最小

Given a graph G = (V, E) with vertex weights w_i ≥ 0, find a min-weight subset of vertices S ⊆ V such that every edge is incident to at least one vertex in S.

★算法1 > Pricing method 竞价法/定价法

Pricing method. Each edge must be covered by some vertex. Edge e = (i, j) pays price p_e ≥ 0 to use both vertex i and j.
竞价法/定价法：每条边都必须被一些节点覆盖。边e = (i, j)支付价格 p_e ≥ 0 来使用顶点i和j

Fairness. Edges incident to vertex i should pay ≤ w_i in total.
公平性：与顶点i相连的每条边的价格之和 ≤ 顶点i权值

Fairness lemma. For any vertex cover S and any fair prices p_e : ∑_e p_e ≤ w(S).
公平性引理：对于任何顶点覆盖S和任何公平的价格p_e，每条边加起来的价格不超过 S中所有顶点的权值

证明：
每条边加起来的价格
≤ S中的每个顶点，与之相连的所有边的价格（每条边至少被算1次）
≤ S中所有顶点的权值（根据公平性）

算法

Set prices and find vertex cover simultaneously.
同时设置价格和查找顶点覆盖。

初始所有边的价格为0
如果有边两个顶点都不是紧的（紧的顶点：一个顶点与之相连的边的价格之和等于顶点权值）
- 选择这样的边
- 增加价格直到两个顶点之一是紧的
- 不断重复直到所有边两个顶点都是紧的

Pricing method example 例子

★Pricing method: analysis 分析

Theorem. Pricing method is a 2-approximation for WEIGHTED-VERTEX-COVER.
定理：带权顶点覆盖问题的竞价法/定价法是2倍近似算法

Pf. 证明

Algorithm terminates since at least one new node becomes tight after each iteration of while loop.
算法会终止，因为每次循环中，至少有一个新顶点变紧
Let S = set of all tight nodes upon termination of algorithm. S is a vertex cover: if some edge (i, j) is uncovered, then neither i nor j is tight. But then while loop would not terminate.
S是算法终止时所有紧的顶点。S是一个顶点覆盖：如果边没有被覆盖，那么它的两个顶点都不是紧的，这种情况在循环终止时不会发生
Let S* be optimal vertex cover. We show w(S) ≤ 2 w(S*).
设S*是最优解，下面证明算法解不超过 2倍最优解

竞价法/定价法算出来的权重
= 所有紧的顶点的权重
= 所有紧的顶点的边的权重之和
≤ 所有顶点的边的权重之和（包括所有顶点）
= 所有边的权重之和的2倍（每条边被2个顶点算过，每条边被算了2次）
≤ 最优解的2倍（最优解中的顶点会至少把每条边算1次）

例题

(2018)叙述带权重的点覆盖问题的竞价法(Pricing method)的步骤。

(2019)简单证明定价算法(Pricing method)求解带权重的点覆盖(Weighted Vertex Cover)问题是2倍近似的。

★算法2 > LP rounding algorithm 线性规划舍入算法

ILP formulation 整数线性规划公式

Integer linear programming formulation.
整数规划公式

Model inclusion of each vertex i using a 0/1 variable x_i
模型对于每个顶点i使用一个0/1变量x_i
$coverx_i= \begin{cases} 0,& \text{if vertex }i\text{ is not in vertex cover}\\ 1,& \text{if vertex }i\text{ is in vertex cover} \end{cases}$
Vertex covers in 1–1 correspondence with 0/1 assignments: S = { i ∈ V : x_i = 1}.
顶点覆盖与0/1指派的对应关系：覆盖的为1
Objective function: minimize Σ_i w_i x_i.
目标函数：最小化每个选中顶点的权值
For every edge (i, j), must take either vertex i or j (or both): x_i + x_j ≥ 1.
对于每条边，至少选一个顶点

Weighted vertex cover 带权顶点覆盖的整数线性规划形式

Weighted vertex cover. Integer linear programming formulation. 带权顶点覆盖的整数规划形式

Observation. If x* is optimal solution to ILP, then S = { i ∈ V : x_i* = 1} is a min-weight vertex cover.
观察：如果x*是整数规划的最优解，那么S是最小的顶点覆盖

Integer linear programming 整数线性规划

Given integers a_ij, b_i, and c_j, find integers x_j that satisfy:
规划n个整数x_j使得c^Tx最小
要求：m个约束条件，对于每个约束条件i，所有整数乘以对应约束条件a_ij的和要大于b_i

a_ij是边-顶点关联矩阵

Observation. Vertex cover formulation proves that INTEGER-PROGRAMMING is an NP-hard search problem.
观察：整数规划是NP难问题

Linear programming 线性规划

Given integers a_ij, b_i, and c_j, find real numbers x_j that satisfy:
和整数规划类似，不过不要求x_j是整数，而是要求x_j是实数

Linear. No x², xy, arccos(x), x(1 – x), etc.
线性：约束条件只有ax ≥ b，没有x², xy, arccos(x), x(1 – x)等

Simplex algorithm. [Dantzig 1947] Can solve LP in practice.
Ellipsoid algorithm. [Khachiyan 1979] Can solve LP in poly-time.
Interior point algorithms. [Karmarkar 1984, Renegar 1988, … ]
Can solve LP both in poly-time and in practice.
实际上上面的算法都可以在多项式时间内解决线性规划问题

LP feasible region 线性规划可行区域

LP relaxation 线性规划松弛

Linear programming relaxation. 线性规划松弛

Observation. Optimal value of LP is ≤ optimal value of ILP.
观察：线性规划的最优值≤整数线性规划的最优值

Pf. LP has fewer constraints.
证明：线性规划的最优值的限制更少

Note. LP is not equivalent to weighted vertex cover. (even if all weights are 1)
注意：线性规划不等价于加权顶点覆盖（即使所有权重均为1）

例如：所有点权值为1，最小的加权顶点覆盖为2，但是线性规划的最优解是3/2（每个顶点选1/2次就可以覆盖所有边至少1次）

Q. How can solving LP help us find a low-weight vertex cover?
问：求解线性规划如何帮助我们找到低权重顶点覆盖？

A. Solve LP and round fractional values.
答：求解线性规划并且舍入分数值

LP rounding algorithm 线性规划舍入算法

Lemma. If x* is optimal solution to LP, then S = { i ∈ V : x_i* ≥ ½} is a vertex cover whose weight is at most twice the min possible weight.
引理：如果x*是线性规划的最优解，那么S是一个顶点覆盖（S选择那些x*中值不小于1/2的顶点），S的权重最多是最优解的2倍

Pf. [S is a vertex cover] 证明S是一个顶点覆盖

Consider an edge (i, j) ∈ E.
对于任意边 (i, j)
Since x_i* + x_j* ≥ 1, either x_i* ≥ ½ or x_j* ≥ ½ (or both) ⇒ (i, j) covered.
因为线性规划要求，两点的值之和不小于1，其中至少一个不小于1/2，那么至少一个会被S选择

Pf. [S has desired cost] 证明S有理想的代价

Let S* be optimal vertex cover. Then
设S*是最优顶点覆盖，那么
S中顶点*的权值之和
≥ S中顶点权值与选择次数相乘之和（线性规划是松弛的，线性规划的最优值 ≤ 整数线性规划的最优值）
≥ S中顶点权值与1/2相乘之和（S中顶点的选择次数都不小于1/2）
≥ 1/2 S中顶点权值之和（提出1/2）

Theorem. The rounding algorithm is a 2-approximation algorithm.
定理：线性规划舍入算法是2倍近似算法

Pf. Lemma + fact that LP can be solved in poly-time.
证明：引理+线性规划可以在多项式时间内解决

★问题 > Knapsack 0-1背包问题的近似算法

0-1背包问题

Knapsack problem.

Given n objects and a knapsack.
n个物体和1个背包
Item i has value v_i > 0 and weighs w_i > 0. (we assume w_i ≤ W for each i)
每个物体有重量和价值（每个物体的重量不超过背包有重量限制W）
Knapsack has weight limit W.
背包有重量限制W
Goal: fill knapsack so as to maximize total value.
目标：填充背包，使物体总价值最大（0-1背包：每个物体只能全部放入或者不放入，不可以放入半个物体等）

Knapsack is NP-complete 0-1背包问题是NP完全的

KNAPSACK. Given a set X, weights w_i ≥ 0, values v_i ≥ 0, a weight limit W, and a target value V, is there a subset S ⊆ X such that:

SUBSET-SUM. Given a set X, values u_i ≥ 0, and an integer U, is there a subset S ⊆ X whose elements sum to exactly U ?

Theorem. SUBSET-SUM ≤_P KNAPSACK.
定理：子集合问题归约到0-1背包问题

Pf. Given instance (u₁, …, u_n, U) of SUBSET-SUM, create KNAPSACK instance:
证明：对于任意子集合问题，构建0-1背包问题的实例：

Knapsack problem: dynamic programming I 0-1背包问题的动态规划解法1

Def. OPT(i, w) = max value subset of items 1,..., i with weight limit w.
定义：OPT(i, w)表示前i个物体中在重量w限制下的最大价值

Case 1. OPT does not select item i.
・OPT selects best of 1, …, i – 1 using up to weight limit w.

Case 2. OPT selects item i.
・New weight limit = w – w_i.
・OPT selects best of 1, …, i – 1 using up to weight limit w – w_i.

Theorem. Computes the optimal value in O(n W) time.

Not polynomial in input size.
不是输入规模的多项式时间算法
Polynomial in input size if weights are small integers.
只有当所有重量都是小整数时才是多项式时间算法

Knapsack problem: dynamic programming II 0-1背包问题的动态规划解法2

Def. OPT(i, v) = min weight of a knapsack for which we can obtain a solution of value ≥ v using a subset of items 1,..., i.
定义：OPT(i, v)表示前i个物体中在价值v限制下的最小重量

Note. Optimal value is the largest value v such that OPT(n, v) ≤ W.
注释：最优值是在OPT(n, v) ≤ W内，找到最大的价值v

Case 1. OPT does not select item i.
情况1：不选择第i个物体

OPT selects best of 1, …, i – 1 that achieves value ≥ v.
和前i-1个物体中最优解选达到价值v的选法相同

Case 2. OPT selects item i.
情况1：选择第i个物体

Consumes weight w_i, need to achieve value ≥ v – v_i.
消耗了重量w_i，要求达到的价值减少了v_i
OPT selects best of 1, …, i – 1 that achieves value ≥ v – v_i.
和前i-1个物体中最优解选达到价值v – v_i的选法相同

Theorem. Dynamic programming algorithm II computes the optimal value in O(n² v_max) time, where v_max is the maximum of any value.
定理：动态规划解法2在O(n² v_max)时间内算出最优值，v_max是所有价值中的最大值

Pf. 证明

The optimal value V* ≤ n v_max.
最优价值不超过n v_max
There is one subproblem for each item and for each value v ≤ V*.
每个物体，对于每个小于V*价值都有一个子问题
It takes O(1) time per subproblem.
每个子问题消耗O(1)时间

Remark 1. Not polynomial in input size!
评论1：不是输入规模的多项式时间算法

Remark 2. Polynomial time if values are small integers.
评论2：只有当所有价值都是小整数时才是多项式时间算法

Polynomial-time approximation scheme 多项式时间近似算法

Intuition for approximation algorithm.
近似算法的直觉

Round all values up to lie in smaller range.
将所有价值舍入到较小范围内
Run dynamic programming algorithm II on rounded/scaled instance.
在舍入/缩放后的实例上运行动态规划算法2
Return optimal items in rounded instance.
返回舍入实例的最优解

Round up all values: 舍入所有价值

0 < ε ≤ 1 = precision parameter.
ε是精度参数，不超过1
v_max = largest value in original instance.
原问题中最大的的价值
θ = scaling factor = ε v_max / 2n.
缩放参数

Observation. Optimal solutions to problem with $vˉ\bar{v}$ are equivalent to optimal solutions to problem with $v^\hat{v}$ .
观察：使用 $vˉ\bar{v}$ 的问题的最优解等价于使用 $v^\hat{v}$ 的问题的最优解

Intuition. $vˉ\bar{v}$ close to $v$ so optimal solution using $vˉ\bar{v}$ is nearly optimal; $v^\hat{v}$ small and integral so dynamic programming algorithm II is fast.
直觉： $vˉ\bar{v}$ 接近 $v$ ，所以最优解接近使用 $vˉ\bar{v}$ 的最优解； $v^\hat{v}$ 是很小的整数，所以动态规划算法2是快的

Theorem. If S is solution found by rounding algorithm and S* is any other feasible solution, then
定理：如果S是近似算法的解，S*是任何其他可行解，那么近似解的价值之和至少是任意解的价值之和的1/(1+ε)

Pf. Let S* be any feasible solution satisfying weight constraint.
证明：S*是任何满足重量限制的可行解

任意解价值总和
≤ 舍入后任意解价值总和（舍入后所有物体价值可能会变大）
≤ 舍入后近似解价值总和（近似解在舍入后是最优的）
≤ 近似解中物体的价值+缩放参数之和（舍入后物体增加的价值不会多于θ）
≤ 近似解中物体的价值之和 + n倍缩放参数（近似解中物体个数不超过n）
= 近似解中物体的价值之和 + 1/2 ε 最大价值（定义）
≤ (1+ε)近似解中物体的价值之和（最大价值≤2近似解中物体的价值之和）

Theorem. For any ε > 0, the rounding algorithm computes a feasible solution whose value is within a 1/(1 + ε) factor of the optimum in O(n³ / ε) time.
定理：对于任意ε>0，近似算法可以在O(n³ / ε)时间内计算出可行解，其值至少是最佳值的1/(1 + ε)

Pf.

We have already proved the accuracy bound.
已经证明准确度
Dynamic program II running time is $O(n2v^max⁡)O(n^2\hat{v}_{\max})$ , where $v^max⁡=⌈vmax⁡θ⌉=⌈2nϵ⌉\hat{v}_{\max}=\lceil\frac{v_{\max}}{\theta}\rceil=\lceil\frac{2n}{\epsilon}\rceil$
动态规划解法2的运行时间为 $O(n2v^max⁡)O(n^2\hat{v}_{\max})$ ，其中 $v^max⁡=⌈vmax⁡θ⌉=⌈2nϵ⌉\hat{v}_{\max}=\lceil\frac{v_{\max}}{\theta}\rceil=\lceil\frac{2n}{\epsilon}\rceil$

★问题 > Generalized load balancing 广义负载均衡

Input. Set of m machines M; set of n jobs J.
输入：m个机器的集合M，n个作业的集合J

Job j ∈ J must run contiguously on an authorized machine in M_j ⊆ M.
作业必须在授权机器上连续运行（作业j的授权机器集合为M_j）
Job j ∈ J has processing time t_j.
作业有处理时长
Each machine can process at most one job at a time.
一台机器同时处理一个作业

Def. Let J_i be the subset of jobs assigned to machine i.
定义：J_i是分配给第i台机器的任务集合

The load of machine i is L_i = Σ_{j∈J_i} tj.
机器i的负载L_i是J_i任务的运行时长之和

Def. The makespan is the maximum load on any machine = max_i L_i.
定义：制造时间时负载最大的机器的负载

Generalized load balancing. Assign each job to an authorized machine to minimize makespan.
广义负载均衡问题：分配作业到授权机器上，使得制造时间最短

Integer linear program and relaxation 整数线性规划和松弛

ILP formulation 整数线性规划形式

LP relaxation 线性规划松弛

不要求在一台机器连续运行

Lower bounds 更低的负载

Lemma 1. The optimal makespan L* ≥ max_j t_j.
引理1：最佳制造时间L* ≥ 最长的作业

Pf. Some machine must process the most time-consuming job.
证明：至少有一台机器处理最长的作业

Lemma 2. Let L be optimal value to the LP. Then, optimal makespan L* ≥ L.
引理2：最佳制造时间L* ≥ 线性规划的最优解

Pf. LP has fewer constraints than ILP formulation.
证明：线性规划有更少的限制条件

Structure of LP solution 线性规划结构

Lemma 3. Let x be solution to LP. Let G(x) be the graph with an edge between machine i and job j if x_ij > 0. Then G(x) is acyclic. (can transform x into another LP solution where G(x) is acyclic if LP solver doesn’t return such an x)
引理3：设x是线性规划的解。图G(x)中，机器和作业存在边当且仅当作业在这台机器上有处理时间。G(x)是无环图。（如果x是有环的，可以把它转化为一个无环的）

Rounding 舍入

Rounded solution. Find LP solution x where G(x) is a forest. Root forest G(x) at some arbitrary machine node r.
舍入解：找到一个解x使得G(x)是森林。让任意机器节点r成为森林的根节点。

If job j is a leaf node, assign j to its parent machine i.
如果作业j是叶子节点，将其分配给父节点机器i
If job j is not a leaf node, assign j to any one of its children.
如果作业i不是叶子节点，将其分配给一个子节点机器

Lemma 4. Rounded solution only assigns jobs to authorized machines.
引理4：舍入算法只把机器分给授权机器

Pf. If job j is assigned to machine i, then x_ij > 0. LP solution can only assign positive value to authorized machines.
证明：如果作业j分配给机器i，那么x_ij > 0。线性规划解只能把正值分配给授权机器

Analysis 分析

Lemma 5. If job j is a leaf node and machine i = parent(j), then x_ij = t_j.
引理5：如果作业j是叶子节点，机器i是它的父节点，那么作业j将完全在机器i上运行t_j时间

Pf.

Since i is a leaf, x_ij = 0 for all j ≠ parent(i).
因为是叶子节点，所有其他机器都没有运行这个作业
LP constraint guarantees Σ_i x_ij = t_j.
线性规划限制保证了运行时间t_j

Lemma 6. At most one non-leaf job is assigned to a machine.
引理6：一个机器只会至多分配一个非叶子作业

Pf. The only possible non-leaf job assigned to machine i is parent(i).
证明：唯一可能的非叶子作业就是机器的父节点

Theorem. Rounded solution is a 2-approximation.
定理：舍入算法是2倍近似算法

Pf.

Let J(i) be the jobs assigned to machine i.
设机器i被分配的作业是J(i)
By LEMMA 6, the load L_i on machine i has two components:
根据引理6，机器i的负载来自两部分：
- 叶子节点：根据线性规划松弛，加起来不超过L，也就不超过L*
- 父节点：只有1个，不超过L*
Thus, the overall load L_i ≤ 2 L*.
因此，所有机器的最大负载≤ 2 L*

Flow formulation 流形式

Flow formulation of LP.
线性规划的流形式

Observation. Solution to feasible flow problem with value L are in 1-to-1 correspondence with LP solutions of value L.
观察：对于值为L的流问题的可行解与值为L的线性规划解是一一对应的

Structure of solution 解的结构

Lemma 3. Let (x, L) be solution to LP. Let G(x) be the graph with an edge from machine i to job j if x_ij > 0. We can find another solution (xʹ, L) such that G(xʹ) is acyclic.
引理3：设(x, L)是线性规划问题的最优解。G(x)是图，边表示机器i做了作业j。可以找到另一个(xʹ, L)，使得图G(xʹ)没有环

Pf. Let C be a cycle in G(x).
证明：设C是G(x)中的一个环

Augment flow along the cycle C. (flow conservation maintained)
沿循环C增加流量（保持流量守恒）
At least one edge from C is removed (and none are added).
至少一条边会被删除（不会添加边）
Repeat until G(xʹ) is acyclic.
重复直到G(xʹ)没有环

Conclusions 结论

Running time. The bottleneck operation in our 2-approximation is solving one LP with m n + 1 variables.
运行时间：2倍近似算法的瓶颈操作是处理m n + 1个变量的线性规划

Remark. Can solve LP using flow techniques on a graph with m + n + 1 nodes: given L, find feasible flow if it exists. Binary search to find L*.
评论：可以在具有m+n+1个节点的图上使用流技术解决LP：给定L，如果存在则找到可行的流。二分搜索查找L*。

Extensions: unrelated parallel machines. [Lenstra–Shmoys–Tardos 1990]

Job j takes tij time if processed on machine i.
2-approximation algorithm via LP rounding.
If P ≠ NP, then no no ρ-approximation exists for any ρ < 3/2

5 Approximation Algorithms 近似算法

Approximation Algorithms 近似算法