论文阅读-Hoogeveen_1991_OR-Letters

作者	年份	近似比
Hoogeveen	1991	$\frac{5}{3}$35​
An, Kleinberg, Shmoys	2012	$\frac{1+\sqrt{5}}{2}$21+5​​
Sebo	2013	$\frac{8}{5}$58​
Rico Zenklusen	2019	1.5

Title: Analysis of Christofides’ heuristic: some paths are more difficult than cycles

Alpha:5/3

TSP定义 略

Christofides’ algorithm for TSP

基本概念

T-joins: 给定点集的子集T, T-join是一个边集, 表示一个子图使得T中的顶点具有奇数度, 不属于T中的顶点具有偶数度.

shortcut: 一个shortcut操作是将两个边{i,j},{j,k}收缩成单个边{i,k}.

ALG1.1

• 计算G上的最小生成树(MST)F
• T是MST上所有具有奇数度的节点集合, 计算T上的最小成本完美匹配M
• 对F ∪ M构成的欧拉图中上的欧拉回路进行短路得到TSP路径

ALG1.2

• 计算G上的最小生成树F
• 计算最短odd(T)-join $J \subseteq E$J⊆E, 其中odd(T)是F上所有度为奇数的节点的集合.
• 对F ∪ J构成的欧拉图中上的欧拉回路进行短路得到TSP路径

Theorem1: Christofide’s algorithm在TSP上的近似比为1.5

proof:

$c(F) < c(C^*)$c(F)<c(C∗), 因为至少比OPT少一条边

如果能够证明$c(M)\leq \frac{1}{2}c(C^{*})$c(M)≤21​c(C∗), 则$c(C^{A}) \leq c(F) + C(M) < \frac{3}{2} c(C^{*})$c(CA)≤c(F)+C(M)<23​c(C∗)

令1,…,2m为T中的奇数度的点, 并假设它们的序号与在$C^*$C∗中出现的顺序一致, 可以将$C^*$C∗中的边划分为一下两个互斥的子集:E1包括{1,2},{3, 4},…{2m-1, 2m}之间的边, E2包括{2,3}, {4, 5},…{2m, 1}之间的边.

对E1, E2中的边集进行shortcut可以得到M1, M2两个matching. $c(M1) + c(M2) \leq c(E1) + c(E2) = c(C^{*})$c(M1)+c(M2)≤c(E1)+c(E2)=c(C∗), 【三角不等式关系使等号成立】,因此存在$c(M) \leq \frac{1}{2}c(C^{*})$c(M)≤21​c(C∗)

Hoogeveen’s algorithm for path-TSP

path TSP定义给定一个TSP输入加上起终点s,t, 找到从s到t的经过所有其他节点的最小费用的路径(Hamilton通路).

ALG2.1

• 令F是G上的MST
• 令T是F中需要被修复的节点的集合:
  • $s$s 当且仅当s在F中具有偶数度
  • $t$t 当且仅当t在F中具有偶数度
  • $v\neq s, t$v​=s,t 当且仅当v具有奇数度
• 找到T上的最小成本完美匹配M
• 在F ∪ M上找一个欧拉通路
• shortcut通路产生一个s-t hamiltonian path.

用T-join代替完美寻找完美匹配

ALG2.2

• 令F是G上的MST
• 令T是F中需要被修复的节点的集合:
  • $s$s 当且仅当s在F中具有偶数度
  • $t$t 当且仅当t在F中具有偶数度
  • $v\neq s, t$v​=s,t 当且仅当v具有奇数度
• 找到T上的最小成本T-join J
• 在F ∪ J上找一个欧拉通路
• shortcut通路产生一个s-t hamiltonian path.

Theorem2: Hoogeveen’s algorithm在path TSP上的近似比为5/3

proof:

令F是MST的边集, $c(F)=\sum_{e \in F} c_e$c(F)=∑e∈F​ce​

令O是最优解的边集, OPT = c(O)
;
有$c(F) \leq OPT$c(F)≤OPT, 因为O也是一个生成树; 令T是F中需要被修复的点的集合

思路: 如果能找到3个T-join使得它们的总成本等于c(F)+OPT, 则有$MST + minimum TJoin \leq c(F) + \frac{1}{3}(c(F) + OPT) \leq OPT + \frac{2}{3}OPT = \frac{5}{3}OPT$MST+minimumTJoin≤c(F)+31​(c(F)+OPT)≤OPT+32​OPT=35​OPT

令r表示MST中一个s-t通路上的边的集合;

对O上的边使用蓝色/绿色交叉上色: 从s开始, 将边变成蓝色遇到第一个T中的点, 接着变换颜色继续上色直到遇到下一个T中的点, 得到两个边集G,B.

F-R 是一个T-join: F∪(F-R)上除了s-t的每个节点都具有偶数度;

G是一个T-join: 将T中的节点两两相连;

B不是一个T-join: F∪B上所有点都具有偶数度, 但是B∪R是一个T-join;

c(F-R) + c(G) + c(B∪R) = c(F) + c(O);

Example

1. 红色边构成R

2. F-R是一个T-join

3. 对OPT上色

4. G和B∪R分别是一个T-join

一些思考 – 为什么可以这样构造:

• 一个欧拉图可以短路成一个Hamilton图, 进而拆成两个matching
• matching一定是T-join
• 在F中一定能找到s-t通路
• 通路和opt构成一个可以构成一个hamilton图, 再按照T短路一个构成两个matching
• 最后, 为什么F去掉这个通路也也一定是一个Tjoin? (F-R)∪F相当于除了s-t通路上的边,其他边都复制一条, 不在通路上的点必定有偶数度,在通路上的点,除s-t以外,都是一进一出,具有偶数度, s-t除去通路包含的边, 具有偶数度,加上后具有奇数度.

上述分析是一个紧的界, 因为可以找到如下例子:

图中标出的边的cost均为1, 其他边的cost等于两点之间的最短路径的cost之和, 最优路径是下方路径, 而算法会按照加粗边加上虚线边的方式走, 之比近似5/3.