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）最小代价连通顶点覆盖可在In n+3内逼近，但不能在（1-ε）In n内逼近（假设NP <$DTIME（n^<O（log log n）>））. 4.针对连通顶点覆盖和连通边控制集，提出了一种2-近似NC（和RNC）算法。5.证明了带需求的部分顶点覆盖问题在因子2内是可逼近的。6.研究了二元加权κ-集覆盖问题.对于代价1和ω且ω [大于或等于] 1.5，证明了3-集覆盖在H（3）- 1/6内是可逼近的;对于代价1和2，证明了κ-集覆盖在H（κ）-1/12内是可逼近的，其中H（κ）表示κ ^κ_<i=I> 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.