本论文研究网络背景下覆盖问题的近似算法,力求设计高效算法并得到好的近似比。主要包括四部分研究。第一部分以无线传感网络为背景,研究最大权预算连通集合覆盖问题(MWBC-SC):给定元素集合E,子集族S(?)2E,权函数w:E→R+,费用函数c:S→R+,以点集S为顶点集的图Gs,正实数L,目标是选择最大权的子集族S’(?)S满足Gs[S’]连通且c(S’)≤ L。针对这一问题,我们给出了一般图上的O(Δlogn)-近似算法和圆盘图上的O(logn)-近似算法,其中△是图的最大度,n是集合的个数。据我们所知,该结果是对最大权预算连通集合覆盖问题的第一个有近似比保证的算法。第二部分以社会网络中的影响传播问题为背景,研究了最小部分集合多重覆盖问题(PSMC):给定元素集E,子集族S(?)2E,费用函数C:S→R+,覆盖次数要求的函数r:E → Z+,正整数k ≤ n,目标是找一个最小费用子集族S’(?)S使得至少有k个元素被完全覆盖,其中元素e被完全覆盖指的是e至少被S’中r(e)个集合覆盖。我们针对这一问题给出了四个近似算法。第一个采用一个简单的贪婪策略得到A-近似比,其中λ = max{|S|:S ∈S}。第二个是一个自然的贪婪算法,采用对偶拟合的分析方法,我们证明了该算法的近似比不超过O(H(λ))。注意到O中包含的常数与较多参数有关,只有当k非常接近于n时才有意义。第三个近似算法是随机算法。可以高概率得到2kρ(rmaxf)+2kρ的近似比,其中f是元素的最大频率,即最多有多少个集合包含同一个元素,rmax是最大覆盖要求,ρ是与集合费用c有关的一个次模函数,kρ是ρ的曲率,用来衡量ρ和模函数的偏差。第四个近似算法采用局部比值法,得到的近似比与算法迭代过程中的覆盖比率有关。特别地,对于部分集合(单重)覆盖和集合(完全)多重覆盖,该算法的近似比均为.f,与经典结果吻合。第三部分以无线传感网络虚拟骨干网的构造为背景,研究一个特殊的覆盖问题,最小d步连通控制集问题(MWdCDS):找一个图G中费用最少的子集C(?)V(G)使得每个在V(G)C中的点到C的距离至多为d,且G中由C导出的子图是连通的。对于MWdCDS,我们给出了两个近似算法。第一个算法得到d(αβ + α + 1)H(△)近似比,其中β是距离小于d的最短连接费用,α是最小点赋权斯坦纳树问题的近似比,△是图的最大度。第二个算法的近似比不超过γ(1 +dH(△))opt,其中ν是距离小于2d的最短连接费用。以上研究呈现出一定的非线性组合优化性质。第四部分我们研究一个非线性组合优化问题,度平衡的支撑树问题:给定图G =(V,E),目标是找一棵支撑树T使得∑v∈VdT(v)2最小,其中dT(v表示v在树T中的度。我们证明了此问题是NP-困难的,并且给出了一个非线性原始对偶算法,得到了max{ +∈,24 Δ+ 1∈-近似比,其中△是图的最大度,∈是任意小的大于0的常数。