Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs
We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-partite hypergraphs.
Source author record
Claus Viehmann
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
3works
2topics
3close collaborators
Published work
3 publications
preprint2010arXiv
Approximating Subdense Instances of Covering Problems
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.
Open access
preprint2010arXiv
Approximating Vertex Cover in Dense Hypergraphs
We consider the minimum vertex cover problem in hypergraphs in which every hyperedge has size k (also known as minimum hitting set problem, or minimum set cover with element frequency k). Simple algorithms exist that provide k-approximations, and this is believed to be the best possible approximation achievable in polynomial time. We show how to exploit density and regularity properties of the input hypergraph to break this barrier. In particular, we provide a randomized polynomial-time algorithm with approximation factor k/(1 +(k-1)d/(k Delta)), where d and Delta are the average and maximum degree, respectively, and Delta must be Omega(n^{k-1}/log n). The proposed algorithm generalizes the recursive sampling technique of Imamura and Iwama (SODA'05) for vertex cover in dense graphs. As a corollary, we obtain an approximation factor k/(2-1/k) for subdense regular hypergraphs, which is shown to be the best possible under the unique games conjecture.
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.