### Page Content

### to Navigation

# Fixed Parameter Approximation for the k-Center Problem in Low Highway Dimension Graphs

**Andreas Emil Feldmann (****Hungarian Academy of Sciences)**

For the k-Center problem a set of k center vertices needs to be found in a graph G with edge lengths, such that the distance from any vertex of G to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded highway dimension, as proposed by Abraham et al. [ICALP 2011]. Intuitively this parameter bounds the number of “access nodes” that all shortest paths pass through.

We show both approximation and fixed-parameter hardness results, and how to overcome them using fixed-parameter approximations, where the two paradigms are combined. In particular, we prove that for any ε > 0 computing a (2−ε)-approximation is W[2]-hard for parameter k, and NP-hard for graphs with highway dimension O(log^{^2} n). The latter does not rule out fixed-parameter (2−ε)-approximations for the highway dimension parameter h, but implies that such an algorithm must have at least doubly exponential running time in h if it exists, unless the ETH fails. On the positive side, we show how to get below the approximation factor of 2 by combining the parameters k and h: we develop a fixed-parameter 3/2-approximation with running time 2^O(kh log h) · n^O(1).

Date | Speaker | Location | Language |
---|---|---|---|

25.11.2015 16:00 | Andreas Emil Feldmann | TEL 512 | English |

Back to the research colloquium site.