知识卡片
修剪误差与列表长度受控
给定n个正整数、目标上限t≥1和误差参数0<ε。令Pᵢ为前i个输入数能形成的全部子集和,Lᵢ为算法修剪后保留且不超过t的列表,δ=ε/(2n)。修剪的关键不变量是:对每个y∈Pᵢ且y≤t,Lᵢ中都有代表z满足
y/(1+δ)ⁱ ≤ z ≤ y。
也就是说,每轮至多再损失一个1+δ因子;经过n轮,最优值y在Lₙ中仍有代表z≥y/(1+δ)ⁿ。算法返回Lₙ最大值z,所以y/z*≤(1+δ)ⁿ。对0<ε,原书把该乘积界为e^(ε/2)≤1+ε,从而得到1+ε近似;其中中间不等式的证明由原书留作练习。
运行时间来自同一个乘法间隔:修剪后相邻正数z1+δ,而所有值都不超过t。因此从最小正整数1增长到t,至多经过约log(1+δ)(t)次,列表长度为O((n/ε)ln t)。合并与修剪对列表长度是线性的,所以总时间关于输入位数、n和1/ε都是多项式。
近似误差由代表不变量控制,列表规模由相邻值的乘法间隔控制;两者合在一起才给出全多项式时间近似方案。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第35章 近似算法 · 查看原书依据
We do so by showing that (1 +ϵ/2n)n ≤ 1 + ϵ. First, inequality (35.23), 0 < ϵ < 1, implies that Next, from equation (3.16) on page 66, we have limn→∞(1 + ϵ/2n)n = eϵ/2. Exercise 35.5-3 asks you to show that Therefore, the function (1 + ϵ/2n)n increases with n as it approaches its limit of eϵ/2, and we have Combining