13 citations · 17 across the 5 of their papers we have counts for
7 papers
Approximation Hardness of Graphic TSP on Cubic Graphs
Marek Karpinski, Richard Schmied
We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the…
New Inapproximability Bounds for TSP
Marek Karpinski, Michael Lampis, Richard Schmied
In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now know…
On Approximation Lower Bounds for TSP with Bounded Metrics
Marek Karpinski, Richard Schmied
We develop a new method for proving explicit approximation lower bounds for TSP problems with bounded metrics improving on the best up to now known bounds. They almost match the be…
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…
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.
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…