A Study on Approximation Algorithm Design Based on Linear Program

目前研究的主要目的是开发基于线性规划松弛的高质量近似算法，用于计算困难的组合优化问题。主要研究结果如下：1.改进的贪婪启发式算法在2/(κ+1)和H(κ)-1/6的因子内证明了多面体的填充和覆盖是可逼近的。2.证明了最小代价边支配集问题在21/(10)内归结为边覆盖可逼近，在2以内可通过更大规模的线性松弛逼近。3.证明了(1)最小代价最大匹配不能在任何多项式可计算因子内逼近(假设P≠NP)，(2)最小代价连通边支配集在3+ε内可逼近，(3)最小代价连通顶点覆盖可以在n+3中逼近，但不能在n中的(L-ε)范围内(假设Np〓DTIME(n^&lt；O(Logn)&gt；))。4.提出了连通顶点覆盖和邻边支配集的2-近似NC(和RNC)算法。5.证明了有需求的带容量的部分顶点覆盖问题在2.6的系数内是可逼近的。考虑了二元加权κ集覆盖问题。对于Costs 1和ω且ω[大于或等于]1.5，3-集合覆盖在H(3)-1/6内是近似的，而对于成本1和2，κ-集合覆盖在H(κ)-1/12内，其中H(κ)表示Σ^κ_&lt；i=i&gt；1/i。

The main purpose of the current research is to develop approximation algorithms of high quality, based on linear program relaxation, for computationally hard combinatorial optimization problems. The summary of major outcomes Is as follows : 1. Polymatroid packing and covering were shown to be approximable, by modified greedy heuristics, within factors of 2/ (κ+1) and H (κ) - 1/6, respectively. 2. The minimum cost edge dominating set problem was shown to be approximable within 21/(10) by reduction to edge cover, and within 2 by a larger scale linear relaxation. 3. It was shown that (1) minimum cost maximal matching cannot be approximated within any polynomially computable factor (assuming P ≠ NP), (2) minimum cost connected edge dominating set is approximable within 3+ε, (3) minimum cost connected vertex cover can be approximated witliin In n+3, but cannot be within (l-ε) In n (assuming NP 〓 DTIME (n^<O(log log n)>)). 4. A 2-approximation NC (and RNC) algorithm was developed for connected vertox cover and counected edge dominating etset. 5. The capacitated partial vertex cover problem with demands was shown to be approximable within a factor of 2. 6. The binary weighted κ-set cover problem was considered. For costs 1 and ω with ω 【greater than or equal】 1.5, 3-set cover was shown approximable within H (3) - 1/6, and for costs 1 and 2, κ-set cover within H (κ) -1/12, where H (κ) denotes Σ^κ_<i=I> 1/i.