Fixed parameter approximations for k-center problems in low highway dimension graphs

DOI10.1007/978-3-662-47666-6_47zbMATH Open1404.68209arXiv1605.02530OpenAlexW2293564405MaRDI QIDQ3449507FDOQ3449507

Authors: Andreas Emil Feldmann 

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: We consider the $k$-Center problem and some generalizations. For $k$-Center 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. [SODA 2010]. 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 $varepsilon>0$ computing a $(2-varepsilon)$-approximation is W[2]-hard for parameter $k$ and NP-hard for graphs with highway dimension $O(lo{g}^{2}n)$. The latter does not rule out fixed-parameter $(2-varepsilon)$-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(khlogh)}cdot{n}^{O(1)}$. Additionally we prove that, unless P=NP, our techniques cannot be used to compute fixed-parameter $(2-varepsilon)$-approximations for only the parameter $h$. We also provide similar fixed-parameter approximations for the weighted $k$-Center and $(k,mathcalF)$-Partition problems, which generalize $k$-Center.

Full work available at URL: https://arxiv.org/abs/1605.02530

Recommendations

• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• The parameterized hardness of the \(k\)-center problem in transportation networks
• The parameterized hardness of the \(k\)-center problem in transportation networks
• \(\mathsf{W[1]}\)-hardness of the \(k\)-center problem parameterized by the skeleton dimension
• Approximating \(k\)-center in planar graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Distance in graphs (05C12)

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Exact and approximation algorithms for clustering
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Easy and hard bottleneck location problems
• VC-dimension and shortest path algorithms
• Highway dimension, shortest paths, and provably efficient algorithms
• Approximation hardness of dominating set problems in bounded degree graphs
• On coresets for k-means and k-median clustering
• Towards fully multivariate algorithmics: some new results and directions in parameter ecology
• Fast Routing in Road Networks with Transit Nodes
• On the computational complexity of centers locating in a graph
• Highway dimension and provably efficient shortest path algorithms
• A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Title not available (Why is that?)
• Search-space size in contraction hierarchies
• On subexponential and FPT-time inapproximability
• Parameterized Approximation Schemes Using Graph Widths

Cited In (16)

• Parameterized approximation algorithms for bidirected Steiner network problems
• On the VC-dimension of unique round-trip shortest path systems
• The parameterized hardness of the \(k\)-center problem in transportation networks
• Parameterized approximation algorithms for some location problems in graphs
• Travelling on graphs with small highway dimension
• Improved PTAS for the constrained \(k\)-means problem
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• Approximating \(k\)-center in planar graphs
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
• Title not available (Why is that?)
• A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• The parameterized hardness of the \(k\)-center problem in transportation networks

Uses Software

• DIMACS

This page was built for publication: Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449507)