algorithm - 了解获得多项式时间算法的几何改进方法

Question

我正在阅读 Network Flows - Theory, Algorithms, and Applications 并且我坚持以下定理的证明（第 3 章，第 67 页）：

定理。假设 ^ 是算法第 ℎ 次迭代中某个最小化问题的某个解的目标函数值，而 ^∗ 是最小目标函数值。此外，假设算法保证对于每次迭代，

(1) (^ - ^(+1)) ≥ (^ - ^∗)

（即，迭代 + 1 处的改进至少是总可能改进的倍数）对于 0 < < 1 的某个常数（与问题数据无关）。然后算法在 (()/) 迭代中终止，其中 是最大和最小目标函数值之间的差。

证明。数量 (^ − ^∗) 表示 ℎ 迭代后目标函数值的总可能改进。考虑从 iteration 开始的 2/ 次迭代的连续序列。如果算法的每次迭代将目标函数值至少提高 (^ − ^∗)/2 个单位，则算法将在这 2/ 次迭代中确定最优解。相反，假设在某个迭代 + 1 时，算法将目标函数值提高了小于 (^ − ^∗)/2 个单位。换句话说，

(2) ^ - ^(+1) ≤ (^ - ^∗)/2。

不等式 (1) 意味着

(3) (^ - ^∗) ≤ ^ - ^(+1)

不等式 (2) 和 (3) 意味着

(^ − ^∗) ≤ (^ − ^∗)/2,

因此该算法已将总可能改进 (^ - ^∗) 减少了至少 2 倍。因此，我们已经证明，在 2/ 次连续迭代内，该算法要么获得最优解，要么将总可能改进减少 1 倍至少 2。由于是最大可能的改进，并且每个目标函数值都是整数，因此算法必须在 (()/) 次迭代内终止。

为什么作者关注2/a迭代？

标签： algorithmoptimizationgraph-algorithm

Answer 1

我认为这样写是为了让计算机科学家更容易理解我们每 2/α 轮将一个整数减半，因此 2/α 轮超轮的数量将为 O(log)。没有特别的原因我们不能更直接地做数学：

T(n) is the gap between the nth solution and an optimal solution.

T(n) ≤ (1 - α) T(n-1) [assumption]


                   n
T(n) ≤ T(0) (1 - α)   [by induction]

              -α n                 x
     < T(0) (e  )     [by 1 + x < e  for x ≠ 0]


                       -α (ln T(0))/α
T((ln T(0))/α) < T(0) e

               = 1,

所以(ln T(0))/α回合就足够了。