6533b834fe1ef96bd129d4a0

RESEARCH PRODUCT

On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric

Ernst AlthausRouven NaujoksJoschka Kupilas

subject

CombinatoricsDiscrete mathematicssymbols.namesakeHamming graphSteiner minimum treeDimension (graph theory)symbolsApproximation algorithmHamming distanceSteiner tree problemMathematics

description

It is known that the d-dimensional Steiner Minimum Tree Problem in Hamming metric is NP-complete if d is considered to be a part of the input. On the other hand, it was an open question whether the problem is also NP-complete in fixed dimensions. In this paper we answer this question by showing that the problem is NP-complete for any dimension strictly greater than 2. We also show that the Steiner ratio is 2 - 2/d for d ≥ 2. Using this result, we tailor the analysis of the so-called k-LCA approximation algorithm and show improved approximation guarantees for the special cases d = 3 and d = 4.

yearjournalcountryeditionlanguage
2011-01-01
https://doi.org/10.1007/978-3-642-20877-5_31