Approximating Subdense Instances of Covering Problems

Details Approximating Subdense Instances of Covering Problems Approximating Subdense Instances of Covering Problems

2010-10-30

arxiv.org/abs/1011.0078v2

Computer Science

Data Structures and Algorithms

Scientific paper

We study approximability of subdense instances of various covering problems on graphs, defined as instances in which the minimum or average degree is Omega(n/psi(n)) for some function psi(n)=omega(1) of the instance size. We design new approximation algorithms as well as new polynomial time approximation schemes (PTASs) for those problems and establish first approximation hardness results for them. Interestingly, in some cases we were able to prove optimality of the underlying approximation ratios, under usual complexity-theoretic assumptions. Our results for the Vertex Cover problem depend on an improved recursive sampling method which could be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Approximating Subdense Instances of Covering Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximating Subdense Instances of Covering Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating Subdense Instances of Covering Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-405320