Local approximations for maximum partial subgraph problem

0.00 Avg rating—0 Votes

Article ID:	iaor20043260
Country:	Netherlands
Volume:	32
Issue:	3
Start Page Number:	217
End Page Number:	224
Publication Date:	May 2004
Journal:	Operations Research Letters
Authors:	Paschos Vangelis Th., Monnot Jrme, Toulouse Sophie

Abstract:

We deal with MAXH0-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio (δ0+1)/(B+2+ν0), where B=maxv∈VdG(v), δ0=minv∈V(H0)dH0(v) and ν0=(|V(H0)|+1)/δ0. Next, we show that this ratio rises up to 3/(B+1) when H0=K3. Finally, we provide hardness results for MAXK3-FREE PARTIAL SUBGRAPH.

Reviews

Required fields are marked *. Your email address will not be published.