顶点覆盖的原始对偶算法
许多具有实际意义的问题都是NP完全问题。我们不知道如何在多项式时间内求得最优解。但是，这些问题往往十分重要，我们不能因此而放弃对它们的求解，即使一个问题是NP完全的，也有它的求解方法。实际应用中，近似最优解一般都能满足要求。返回近似最优的方法称为近似算法。
前言
顶点覆盖问题是一个NP完全判定问题的最优化形式。虽然在一个图G中寻找最优顶点覆盖比较困难，但是找出近似最优的顶点覆盖还是相对容易的。在没有权重的图里面顶点覆盖问题，只考虑每个边至少与一个顶点覆盖的点相连，但对有权重的顶点覆盖问题是找出带顶点权重和的最小值。
问题描述
给定一个赋权无向图G=(V,E)，每个顶点v∈V都有一个权值c(v)。如果U⊆V，且对任意（u,v）∈E有u∈U或v∈U，就称U为图G的一个顶点覆盖。G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖。
理论回顾
到现在为止，我们前面知道如何机械地寻找任何
L
P
LP
LP的对偶的一切。然而，这里有一些直觉来帮助这个过程。我们从覆盖线性规划
L
P
LP
LP开始，就像上面的一样，首先给
L
P
LP
LP中的每个约束赋予一个变量
y
i
y_i
yi（不包括
x
j
≥
0
x_j\ge0
xj≥0的约束）。写下目标很容易。唯一棘手的部分是对偶约束，
y
⊤
A
≤
c
⊤
\mathbf{y}^\top A\le \mathbf{c} ^\top
y⊤A≤c⊤
现在，让我们固定一个坐标
c
c
c，比如说
j
j
j，并计算出形式
∑
(
.
.
.
)
≤
c
j
\sum(...)\le c_j
∑(...)≤cj,注意
y
⊤
A
\mathbf{y}^\top A
y⊤A是一个行向量，它的第
j
j
j个坐标是
y
y
y和
A
A
A的第
j
j
j列的点积，我们用
a
j
c
a_{j}^{c}
ajc来表示，该列包含变量
x
j
x_j
xj的系数。这样我们得到约束
y
⊤
a
j
c
≤
c
j
\mathbf{y}^\top a_{j}^{c}\le c_j
y⊤ajc≤cj,最后，我们保证
y
i
y_i
yi是非负的。为了使具体化，我们考虑顶点覆盖问题
（
L
P
）
（LP）
（LP），这里，我们给定了一个无向图
G
=
(
V
,
E
)
G=(V,E)
G=(V,E)，它的边是顶点的集合，每个顶点的大小为2，我们将变量
x
v
x_v
xv与每个顶点相关联，并将
x
v
x_v
xv解释为解中包含顶点
v
v
v，顶点覆盖问题的原始规划问题如下：
我们将对偶变量
y
e
y_e
ye赋予约束
∑
v
∈
e
x
v
≥
1
\quad \sum_{v\in e}x_v \ge1
∑v∈exv≥1，因为对于所有的
e
e
e，
b
e
=
1
b_e=1
be=1，所以对偶目标是
m
a
x
∑
e
y
e
⋅
1
max\sum_e y_e\cdot 1
max∑eye⋅1现在考虑
v
v
v对应的对偶约束，
y
⊤
a
v
c
≤
c
v
\mathbf{y}^\top a_{v}^{c}\le c_v
y⊤avc≤cv我们可以把这个写成
∑
e
y
e
a
e
,
v
≤
c
v
\sum_e y_ea_{e,v}\le c_v
∑eyeae,v≤cv,因为当
e
e
e与
v
v
v相关联，
a
e
,
v
=
1
a_{e,v}=1
ae,v=1，否则
a
e
,
v
=
0
a_{e,v}=0
ae,v=0，我们可以把约束条件写成
∑
e
∈
δ
(
v
)
y
e
≤
c
v
\sum_{e\in \delta(v)}y_e\le c_v
∑e∈δ(v)ye≤cv，最后的结果
在我们讨论原始对偶算法之前，观察强对偶性作为极大极小关系是有用的。事实上，许多极大极小关系都可以相对容易地由它证明。例如，冯洛伊曼的极大极小定理可以很容易地由它推导出来，如果你意识到最大流与最小割对偶，并且最小割具有整数基本可行解，那么最大流最小割定理也正好来自于LP对偶性。考虑顶点覆盖，如果对于某些对偶可行解
y
y
y，我们可以用
ρ
⋅
∑
e
y
e
\rho \cdot\sum_e y_e
ρ⋅∑eye限定某些定点覆盖
S
S
S的代价，那么我们立即通过弱对偶性得到一个
ρ
\rho
ρ近似。
∑
v
∈
S
c
v
≤
ρ
⋅
∑
e
y
e
≤
ρ
⋅
O
P
T
V
C
L
P
≤
ρ
⋅
O
P
T
V
C
I
P
\sum_{v\in S}c_v\le\rho\cdot\sum_e y_e\le\rho\cdot OPT_{VC_{LP}}\le\rho\cdot OPT_{VC_{IP}}
v∈S∑cv≤ρ⋅e∑ye≤ρ⋅OPTVCLP≤ρ⋅OPTVCIP
所以我们把对偶变量看做是提供金钱，特别是
∑
e
y
e
\sum_e y_e
∑eye,并允许算法花费最多
ρ
⋅
∑
e
y
e
\rho \cdot\sum_e y_e
ρ⋅∑eye来购买一个顶点的覆盖。
作为一个简单的例子，考虑我们有一个未加权的顶点覆盖实例
G
G
G，我们找到一个匹配
M
M
M的最大基数，并设
y
y
y为
M
M
M的特征向量，即如果
e
∈
E
e \in E
e∈E,则
y
e
=
1
y_e=1
ye=1，否则
y
e
=
0
y_e=0
ye=0。注意
y
y
y是对偶可行的，现在，我们用
y
y
y来决定买什么顶点来做我们的顶点覆盖，如下所示：如果
v
v
v与
M
M
M的某个顶点相关联，买它，否则不买。设
S
S
S是顶点的输出集合，那么
S
S
S是一个顶点覆盖，因为如果它不是，一些边
e
e
e可以添加到
M
M
M，这与它是最大基数的事实相矛盾。现在，每条边
e
=
{
u
,
v
}
∈
M
有
y
e
=
1
e=\{u,v\}\in M有y_e=1
e={u,v}∈M有ye=1,所以如果我们把
u
u
u和
v
v
v的成本记在
e
=
{
u
,
v
}
e=\{u,v\}
e={u,v}上，我们花费有
2
y
e
2y_e
2ye。得出
∑
v
∈
S
c
v
≤
2
⋅
∑
e
y
e
\sum_{v\in S}c_v\le2\cdot\sum_e y_e
∑v∈Scv≤2⋅∑eye。
我们通常按照以下方式使用原始对偶模式设计算法（用于最小化问题）：
(1)写下一个LP松弛问题，并找出它的对偶。试着为对偶变量找到一些直观的意义。
(2)从向量
x
=
0
x=0
x=0，
y
=
0
y=0
y=0开始，这是对偶可行的，但原始不可行。
(3)直到原始可行
a
a
a.以某种控制的方式增加对偶值
y
i
y_i
yi，直到某些对偶约束变紧
（
∑
i
y
i
a
i
j
=
c
j
）
（\sum_i y_i a_{ij} =c_j）
（∑iyiaij=cj），同时始终保持
y
y
y的对偶可行性。
b
b
b.选择紧对偶约束的某个子集，并将其对应的原始变量增加一个整数。
(4)为了进行分析，证明输出向量对
(
x
,
y
)
(x,y)
(x,y)在
ρ
\rho
ρ值尽可能小的情况下满足
c
⊤
x
≤
ρ
⋅
y
⊤
b
\mathbf{c}^\top x\le \rho\cdot\mathbf{y}^\top b
c⊤x≤ρ⋅y⊤b，在决定如何提高对偶变量和原始变量时，要记住这个目标。
顶点覆盖的原始对偶算法
我们将应用原始-对偶模式来给出带有加权顶点代价的顶点覆盖的2-近似。得到以下算法：
设 x x x， y y y是上述算法输出的向量，那么 x x x是原始可行的， y y y是对偶可行的。
证明:
从
E
E
E中删除的每条边都与某个顶点
v
v
v相关联，使得
x
v
=
1
x_v=1
xv=1。只有当每条边都被删除时，算法才会终止。因此，对于所有的
e
∈
E
e\in E
e∈E，有
∑
v
∈
e
x
v
≥
1
\sum_{v\in e}x_v\ge1
∑v∈exv≥1,
x
x
x是可行的，至于
y
y
y，没有违反任何约束，因为一旦约束变紧，约束中的边将被删除，因此它们的
y
e
y_e
ye值不会进一步提高。
设
x
x
x，
y
y
y为上述算法输出的向量，那么
c
⊤
x
≤
2
⋅
(
y
⊤
⋅
1
)
\mathbf{c}^\top x\le 2\cdot(\mathbf{y}^\top \cdot1)
c⊤x≤2⋅(y⊤⋅1)
证明:设
A
=
{
v
∣
x
v
=
1
}
A=\{v|x_v=1\}
A={v∣xv=1}，则
第二行遵循的事实是，我们只对紧对偶约束对应的顶点
v
v
v设置
x
v
=
1
x_v=1
xv=1。也就是说，
v
∈
A
v\in A
v∈A隐含着
∑
e
∈
δ
(
v
)
y
e
=
c
v
\sum_{e\in \delta(v)}y_e= c_v
∑e∈δ(v)ye=cv,第三行只是简单地调换了求和的顺序，最后一行是根据所有
e
e
e的
∣
e
∣
=
2
|e|=2
∣e∣=2得出的结论。
上面是的算法是加权顶点覆盖的2-近似。
证明 ：观察到如果我们选择 E ′ E^{\prime} E′为单个边，那么我们就得到了顶点覆盖的局部比算法。注意，在这种情况下，近似保证的证明是很简单的，不需要归纳。然而，我们可以用一个归纳证明来说明，在任何时候，我们所付出的成本都不超过我们从对偶中“收集“到的代价的两倍。 c ⊤ x ≤ 2 ⋅ ( y ⊤ ⋅ 1 ) \mathbf{c}^\top x\le 2\cdot(\mathbf{y}^\top \cdot1) c⊤x≤2⋅(y⊤⋅1)，而不仅仅是在执行结束时，这种思想在分析一些原始对偶算法时很有用。
顶点覆盖的原始对偶算法起源于Bar Yehuda和Even(1981)[1] ，尽管它最初并没有被描述为一个原始-对偶算法，但回想起来，这是第一次在近似算法中使用该模式。Kuhn(1955) [4] 给出了第一个原始的对偶算法，用于加权二分匹配问题，然而，他用“匈牙利方法”来描述他的算法。Dantzig、Ford和Fulkerson (1956)[5] 用这种方法给出了求解线性规划的另一种方法，并称之为原始对偶方法。尽管该模式在求解线性规划方面并不十分成功，但它很快在组合优化中得到了广泛的应用，Agrawal、Klein和Ravi (1995)[8] 以及Goemans和Williamson (1995)[7] 的作品在后一种情况下恢复了这种模式的使用，并引入了以同步方式生长对偶的强大思想。放松互补松弛条件的机制首先在Williamson、Goemans、Mihail和Vazirani(1995) [9] 中形成。更多历史信息，请读者参见Goemans和Williamson(1997)[6] 。
总结
以上就是今天要讲的内容，本文仅仅简单介绍了原始对偶模式在顶点覆盖问题中的使用，而原始对偶模式提供了大量能使我们快速解决NP-难问题的近似算法。文章来源：https://www.toymoban.com/news/detail-776240.html
参考文献
[1] R. Bar-Yehuda and S. Even. A linear time approximation algorithm for the weighted vertex
cover problem. Journal of Algorithms, 2:198–203, 1981.
[2] Michel X. Goemans and David P. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In Dorit Hochbaum, editor, Approximation algorithms for NP-hard problems, chapter 4, pages 144–191. PWS Publishing Co., Boston, MA, USA, 1997.
[3] D. Williamson. The primal-dual method for approximation algorithms. Mathematical Programming, Series B, 91(3):447–478, 2002.
[4] H.W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2:83–97, 1955.
[5] G.B. Dantzig, L.R. Ford, and D.R. Fulkerson. A primal–dual algorithm for linear programs. In H.W. Kuhn and A.W. Tucker, editors, Linear Inequalities and Related Systems, pages 171–181. Princeton University Press, Princeton, NJ, 1956.
[6] M.X. Goemans and D.P. Williamson. The primal–dual method for approximation algorithms and its applications to network design problems. In D.S.
Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pages 144–191. PWS Publishing, Boston, MA, 1997.
[7] M.X. Goemans and D.P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24:296–317, 1995.
[8] A. Agrawal, P. Klein, and R. Ravi. When trees collide: an approximation algorithm for the generalized Steiner network problem on networks. SIAM Journal on Computing, 24:440–456, 1995.
[9] D.P. Williamson, M.X. Goemans, M. Mihail, and V.V. Vazirani. A primal– dual approximation algorithm for generalized Steiner network problems. Combinatorica, 15:435–454, 1995.文章来源地址https://www.toymoban.com/news/detail-776240.html
到了这里，关于近似算法之——顶点覆盖的原始对偶算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
