以下答案可能是错的，仅供参考。

1

假设该问题和互补问题的解的和为 n。对于该问题，已知 A(I)/OPT(I) ≤ k，则对于互补问题，OPT’(I)/A’(I)=(n-OPT(I))/(n-A(I))≤(n-OPT(I))/(n-kOPT(I))=(n/OPT(I)-1)/(n/OPT(I)-k)

而 n/OPT(I) 不一定是常数项。

2

已知渐进性能比 ≤ 绝对性能比。对于 scaling 的问题，OPT(I^(k))=kOPT(I)，因此需要证明渐进性能比不会小于绝对性能比。可以得到如果是这样子，那么 A(I^k) < kA(I)，但是我们知道在输入规模扩大 k 倍之后这个近似计算的规模也至少会相应扩大这么多，所以这个不等式不成立。

3

MST 是先找最小生成树，然后树边复制，然后找欧拉图，然后欧拉图短路/剪枝的算法。

需要构造一个满足 $\Delta$TSP 条件的实例。？

4

u, v 最短路径问题 ⇒ u, v 是否存在长度为 k 的路径

O(n)

5

1. 对于消息 M，除了第一次接收的信道以外，其他的边都传了两次，所以 M 一共发送了 图边数2-(n-1) 次。每次传送 M 都会产生对应的 <parent> 或 <reject> 信息，所以总信息数 = 2(图边数*2-(n-1))≤2(n(n-1)-(n-1))=2(n-1)^2
2. 消息复杂性为 O(n^2)=O(m)；时间复杂性为 O(D)
3. 区别是同步模型是按照轮来运行的。构造出的是 BFS。归纳法证明。

6

LV 算法返回正确解或者运行失败。设计如下：

1. 随机挑选图中的 k 条不组成环的边作为哈密顿回路的一部分