Week 7: The Steiner Forest Problem Problem Definition给定联通无向图$(V, E)$和若干个terminals的集合$S_i = \{t_{i,1}, t_{i,2}, \cdots, t_{i, k_i} \}$, 要求选出边权和最小的边,使得任意$S_i$中的点联通。 Case Study: Steiner Tree考虑只有一个集合$S = \{t_1, t_2 \cdots t_k\}$, 要使得集合内部的点联通。 这个问题在ACM/ICPC竞赛见过,一般用动态规划来解决。 最终答案一定是一棵生成树,因此可以用动态规划的思想一步步构造出 ...
Approximation Algorithm(6)-Linear Programming Duality
Week 6: Linear Programming Duality 本周学习的内容是利用线性规划的对偶来设计近似算法。 Introduction考虑下面一个线性规划问题: \begin{split} &\min 7x_1 + x_2 + 5x_3 \\ &x_1-x_2+3x_3 &\geq 10 \ \ &(1)\\ &5x_1 + 2x_2 - x_3 &\geq 6 &(2) \\ &x_1, x_2, x_3 &\geq 0 &(3,4,5) \end{split}$2*(1) + (2)$ 可以得到$7x_1 + 5x_3 \geq 26$。 因此目标函数$7x_1+x_2+5 ...
Approximation Algorithm(5)-The MultiwayCut Problem
Week 5: The MultiwayCut Problem Problem Definition给出一个边权非负的无向图$G = (V, E)$, 其中有$k$个顶点是terminals(之后记为$a_1 \cdots a_k, A := \{a_i\}$)。删掉边集$E’ \subset E$, 使得这$k$个顶点互相不连通,要求$weight(E’)$尽可能小。实际上,问题等价于将点集$V$划分为$k$个集合,每个terminal各自属于一个集合,代价是跨过集合的边。 Trivial Case: $k= 2$经典问题,最大流=最小割,分别以两个terminals为源点和汇点做最大流。 ...
Project Euler Problem 550-Divisor Game
Problem有$N$个大于等于2的正整数,两个人博弈,轮到某个人的回合,他需要选择其中一个数$X$,将它移走,然后加入两个新的正整数$X1, X2$, 满足$2\leq X1, X2 \lt N $ 并且$X1, X2$都是$X$的约数。 不能操作的人判定为失败。假定两个人都按照最优策略,问有多少种局面$a_1, a_2 \cdots a_{10^{12}}$, 满足$2 \leq a_i \leq 10^7$并且先手必胜。 Solution显然这是一个组合游戏,可以利用SG函数来判断谁必胜。 根据SG定理整个游戏的SG值等于各个子游戏的SG异或起来,因此只要知道如何计算$SG(n)$, 即 ...
Stoer–Wagner Algorithm
Download Paper: A Simple Min-Cut Algorithm The Problem将一个带非负边权的无向图$G = (V, E)$分成2个非空点集$S, T$, 使得跨过$S, T$的边权值之和尽可能小, 即求 \mathop{\arg\min}\limits_{S, T}{\sum\limits_{(u,v)\in E \\ u\in S, v\in T}{w(u, v)}}以前只学过网络流求$s-t$最小割, 而这个问题要求的是全局的最小割。这篇paper介绍的Stoer–Wagner Algorithm其实很早就听说过了,于是趁着暑假看了看。其实算法的思想和过 ...
Project Euler Problem 379-Least common multiple count
Problem:求有多少正整数对$(x, y)$满足$x \leq y$并且$x, y$的最小公倍数$\leq 10^{12}$. Solution:为了方便,先去掉$x \leq y$的限制: 设$N = 10^{12}$, 那么原问题的答案 = (去掉 $x\leq y$的限制后的答案+N) / 2. 枚举$(x, y)$的最大公约数$d$,即$x = id, y = jd$, 最小公倍数就是$ijd$, 当然还要求$i, j$互质。 令$[expression]$表示当表达式为真的时候是1,否则是0。 $(i, j)$表示$i,j$的最大公约数)。 $h(n) = \sum\limi ...
Approximation Algorithm(4)-The Set Cover Problem
Week 4: The Set Cover Problem Problem Definition定义元素的集合$E = \{e_1, e_2 \cdots e_n \}$, 给出$m$个集合$\{S_i \subseteq U \}$, 且$\bigcup\limits_{i=1}^{m}{S_i} = E$。 选取第$i$个集合需要代价$c_i$, 求集合$I$, 满足$\bigcup\limits_{i \in I}{S_i} = E$ 并且 $\sum\limits_{i \in I}{c_i}$最小。容易发现, Week 1讲的Vertex Cover问题是Set Cover问题的一 ...
Approximation Algorithm(3)-The Binpacking Problem
Week 3: The Binpacking Problem Problem Definition:本周讲的问题和上周背包问题有点相似,上周的是给出物品的体积和价值,要装到一个背包里使得价值之和尽可能大。本周的问题是$N$件物品,每件物品有一个体积$\{s_i\}$, 不失一般性地,可以约定$\{s_i\} \leq 1$, 有容量为$1$箱子, 要用尽可能少的箱子容纳所有的物品。 课程内容: Next Fit Algorithm: Algorithm: 依次考虑每个物品, 如果这个物品能放入当前箱子, 就放入, 否则关闭当前箱子, 打开一个新的箱子放入这个物品。 Approximation ...
Approximation Algorithm(2)-The Knapsack Problem
Week 2: The Knapsack Problem Problem Definition:$N$件物品,每件物品有一个体积$\{s_i\}$和价值$\{v_i\}$, 现在有一个容量是$B$的背包,要选一些物品装进背包,使得价值之和最大。约定不会有体积超过背包容积的物体。 已有知识:各种背包问题的动态规划做法。 课程内容: Special Case 1:物品的体积等于价值. 也就是说,要将背包装得尽可能满。 贪心做法: 按体积从大到小选。因为有物品装不进背包的时候,背包至少是half-full的,所以近似度是2. Special Case 2: 物品价值都比较小. 考虑动态规划,$d ...