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

DOI10.1007/978-3-662-47666-6_47MaRDI QIDQ3449507zbMATH OpenOpenAlexFDO

Authors Andreas Emil Feldmann

Publication date 4 November 2015

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

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

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)

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.

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

Cites work

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

Cited in

(15)

• Approximating \(k\)-center in planar graphs
• The parameterized hardness of the \(k\)-center problem in transportation networks
• scientific article; zbMATH DE number 7278055 (Why is no real title available?)
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
• Improved PTAS for the constrained \(k\)-means problem
• A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• On the VC-dimension of unique round-trip shortest path systems
• Parameterized approximation algorithms for bidirected Steiner network problems
• 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
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• Travelling on graphs with small highway dimension
• The parameterized hardness of the \(k\)-center problem in transportation networks

Describes a project that uses

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)