13 citations · 17 across the 5 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.CC2011★ 3 cited
Improved Lower Bounds for the Shortest Superstring and Related Problems
Marek Karpinski, Richard Schmied
We study the approximation hardness of the Shortest Superstring, the Maximal Compression and the Maximum Asymmetric Traveling Salesperson (MAX-ATSP) problem. We introduce a new red…
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.