Local approximations for maximum partial subgraph problem

被引：0
作者：
Monnot, J [1 ]
Paschos, VT [1 ]
Toulouse, S [1 ]
机构：
[1] Univ Paris 09, LAMSADE, F-75775 Paris 16, France
来源：
OPERATIONS RESEARCH LETTERS | 2004年 / 32卷 / 03期
关键词：
approximation algorithms; local search; APX-complete; maximum subgraph problem; minimum vertex deletion problem; hereditary property;
D O I：
10.1016/j.orl.2003.08.004
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We deal with MAX H-0-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio (delta(0) + 1)/(B + 2 + nu(0)), where B = max(nuis an element ofV)dG(nu), delta(0) = min(nuis an element ofV(H0))d(H0)(nu) and nu(0) = (\V(H-0)\ + 1)/delta(0). Next, we show that this ratio rises up to 3/(B + 1) when H-0 = K-3. Finally, we provide hardness results for MAX K-3-FREE PARTIAL SUBGRAPH. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码：217 / 224
页数：8
相关论文
共 14 条
12