1 citations · 1 across the 3 of their papers we have counts for
3 papers
cs.DS2011
Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs
Marek Karpinski, Richard Schmied, Claus Viehmann
We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-partite hypergraphs.
cs.DS2010★ 1 cited
Approximating Vertex Cover in Dense Hypergraphs
Jean Cardinal, Marek Karpinski, Richard Schmied +1
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 freque…
cs.DS2010
Approximating Subdense Instances of Covering Problems
Jean Cardinal, Marek Karpinski, Richard Schmied +1
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 funct…