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

Question

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

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

(1) (^ − ^(+1)) ≥ (^ − ^∗)

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

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

(2) ^ − ^(+1) ≤ (^ − ^*)/2.

不等式 (1) 意味着

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

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

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

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

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

Answer 1

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

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))/α轮就够了。

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

Understanding geometric improvement approach for obtaining polynomial-time algorithms

algorithm

optimization

graph-algorithm