权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

A Study on Approximation Algorithm Design Based on Linear Program

基于线性规划的逼近算法设计研究

基本信息

批准号：
13680409
负责人：
FUJITO Toshihiro
金额：
$ 0.77万
依托单位：
NAGOYA UNIVERSITY
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680409/
关键词：
NP-hard problem Approximation Algorithm Packing Problem Covering problem Greedy heuristic Edge Dominating Set problem Set Cover problem Linear program relaxation マトロイド頂点被覆問題貪欲解法(グリーディ法)

项目摘要

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.

目前研究的主要目的是开发高质量的近似算法，基于线性规划松弛，计算困难的组合优化问题。主要研究结果如下：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。