Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2012 Copyright 2012 University of Bonn, Department of Computer Science, Chair V

89134 On Approximation Lower Bounds for TSP with Bounded Metrics
Marek Karpinski and Richard Schmied
[Download PostScript] [Download PDF] [Abstract]
89135 Approximate Counting of Matchings in Sparse Hypergraphs
Marek Karpinski, Andrzej Rucinski and Edyta Szymanska
[Download PostScript] [Download PDF] [Abstract]
89136 Approximability of the Vertex Cover Problem in Power Law Graphs
Mikael Gast, Mathias Hauptmann
[Download PostScript] [Download PDF] [Abstract]
89137 Approximate Counting of Matchings in Sparse Uniform Hypergraphs
Marek Karpinski, Andrzej Rucinski and Edyta Szymanska
[Download PostScript] [Download PDF] [Abstract]
89138 Optimal Cuts and Bisections on the Real Line in Polynomial Time
Marek Karpinski, Andrzej Lingas and Dzmitry Sledneu
[Download PostScript] [Download PDF] [Abstract]
89139 Improved Inapproximability Results for the Shortest Superstring and Related Problems
Marek Karpinski and Richard Schmied
[Download PostScript] [Download PDF] [Abstract]
89140 Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs
and Some Generalizations

Mikael Gast, Mathias Hauptmann and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
89141 Optimal Cuts and Partitions in Tree Metrics in Polynomial Time
Marek Karpinski, Andrzej Lingas and Dzmitry Sledneu
[Download PostScript] [Download PDF] [Abstract]
89142 Inapproximability of Dominating Set in Power Law Graphs
Mikael Gast, Mathias Hauptmann and Marek Karpinski
[Download PostScript] [Download PDF] [Abstract]
Last Change: 12/17/12 at 09:11:33
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V