
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2010  Copyright 2010 Universität Bonn, Institut für Informatik, Abt. V  
85315 14.10.2010 
On Approximation Complexity of Metric Dimension Problem
Mathias Hauptmann, Richard Schmied and Claus Viehmann [Download PostScript] [Download PDF]
We study the approximation complexity of the Metric Dimension problem in bounded degree, dense as well as in general graphs. For the general case, we prove that the Metric Dimension problem is not approximable within (1ε) ln(n) for any ε > 0, unless NP ⊆ DTIME(n^{log(log(n))}), and we give an approximation algorithm which matches the lower bound. 

Last Change:
11/05/14 at 10:53:08
English 
Universität Bonn > Institut für Informatik > Abteilung V 