Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2010 Copyright 2010 Universität Bonn, Institut für Informatik, Abt. V
89126

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(nlog(log(n))), and we give an approximation algorithm which matches the lower bound.
Even for bounded degree instances it is APX-hard to determine (compute) the value of the metric dimension which we prove by constructing an approximation preserving reduction from the bounded degree Vertex Cover problem.
The special case, in which the underlying graph is superdense turns out to be APX-complete. In particular, we present a greedy constant factor approximation algorithm for these kind of instances and construct an approximation preserving reduction from the bounded degree Dominating Set problem. We also provide first explicit approximation lower bounds for the Metric Dimension problem restricted to dense and bounded degree graphs.

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

Powered by Zope