Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
From MaRDI portal
Publication:3449507
DOI10.1007/978-3-662-47666-6_47zbMath1404.68209arXiv1605.02530OpenAlexW2293564405MaRDI QIDQ3449507
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
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (11)
Unnamed Item ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ On the VC-dimension of unique round-trip shortest path systems ⋮ Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack ⋮ Unnamed Item ⋮ The Parameterized Hardness of the k-Center Problem in Transportation Networks ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Approximation hardness of dominating set problems in bounded degree graphs
- Easy and hard bottleneck location problems
- Exact and approximation algorithms for clustering
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- On subexponential and FPT-time inapproximability
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- VC-Dimension and Shortest Path Algorithms
- Fast Routing in Road Networks with Transit Nodes
- Highway Dimension and Provably Efficient Shortest Path Algorithms
- A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- On coresets for k-means and k-median clustering
- Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
- On the computational complexity of centers locating in a graph
- Parameterized Approximation Schemes Using Graph Widths
- Search-Space Size in Contraction Hierarchies
This page was built for publication: Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
