Polynomial time approximation schemes for clustering in low highway dimension graphs

DOI10.1016/J.JCSS.2021.06.002OpenAlexW3185122763MaRDI QIDQ2229951FDOQ2229951

Authors: Andreas Emil Feldmann, David Saulpic 

Publication date: 17 September 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

Recommendations

• Polynomial time approximation schemes for clustering in low highway dimension graphs
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
• Travelling on graphs with small highway dimension

zbMATH Keywords

clusteringapproximation algorithmhighway dimension

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• A 1.488 approximation algorithm for the uncapacitated facility location problem
• Greedy Strikes Back: Improved Facility Location Algorithms
• A new greedy approach for facility location problems
• Title not available (Why is that?)
• VC-dimension and shortest path algorithms
• Highway dimension, shortest paths, and provably efficient algorithms
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• The hardness of approximation of Euclidean \(k\)-means
• Bypassing the embedding
• Highway dimension and provably efficient shortest path algorithms
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Hierarchy of Transportation Network Parameters and Hardness Results
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• Title not available (Why is that?)
• Travelling on graphs with small highway dimension

Cited In (1)

• Generalized \(k\)-center: distinguishing doubling and highway dimension

This page was built for publication: Polynomial time approximation schemes for clustering in low highway dimension graphs

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