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）之内，最低成本优势占主导地位的设置问题在21/（10）之内与较大规模的线性松弛范围内相似。 3. It was shown that (1) minimum cost maximum matching cannot be approximated within any polynomically 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。为连接的vertox覆盖物和连接的边缘主导ETCET开发了2个附属物NC（和RNC）算法。 5。在2.6倍以下的电容部分顶点覆盖问题上与需求相似。对于成本为1和ω的ω[大于或相等] 1.5，在H（3）-1/6中显示了3键覆盖物，对于1和2的成本，H（κ）-1/12中的κ -ster覆盖率为1和2，其中H（κ）表示σ^^κ____<i = i> 1/i> 1/i/i。