On the public citation graph

Near-linear Time Approximation Schemes for Clustering in Doubling Metrics

https://doi.org/10.1145/3477541
0 signed · 57 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-63248-4_5openalex-snapshot
Nearly linear time approximation schemes for Euclidean TSP and other geometric problems
inferredcites →https://doi.org/10.1007/978-3-662-48350-3_72openalex-snapshot
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
inferredcites →https://doi.org/10.1007/s004540010019openalex-snapshot
On Approximate Geometric k -Clustering
inferredcites →https://doi.org/10.1007/s10878-009-9216-yopenalex-snapshot
Polynomial time approximation schemes for minimum disk cover problems
inferredcites →https://doi.org/10.1016/j.comgeo.2004.03.003openalex-snapshot
A local search approximation algorithm for k-means clustering
inferredcites →https://doi.org/10.1016/j.ic.2012.01.007openalex-snapshot
A 1.488 approximation algorithm for the uncapacitated facility location problem
inferredcites →https://doi.org/10.1016/j.tcs.2010.05.034openalex-snapshot
The planar k -means problem is NP-hard
inferredcites →https://doi.org/10.1109/focs.2013.80openalex-snapshot
A Linear Time Approximation Scheme for Euclidean TSP
inferredcites →https://doi.org/10.1109/focs.2015.52openalex-snapshot
A Light Metric Spanner
inferredcites →https://doi.org/10.1109/focs.2016.46openalex-snapshot
Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
inferredcites →https://doi.org/10.1109/focs.2016.47openalex-snapshot
Local Search Yields a PTAS for $k$-Means in Doubling Metrics
inferredcites →https://doi.org/10.1109/focs.2016.91openalex-snapshot
A PTAS for the Steiner Forest Problem in Doubling Metrics
inferredcites →https://doi.org/10.1109/focs.2017.14openalex-snapshot
On the Local Structure of Stable Clustering Instances
inferredcites →https://doi.org/10.1109/focs.2017.15openalex-snapshot
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
inferredcites →https://doi.org/10.1109/focs.2018.00082openalex-snapshot
Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics
inferredcites →https://doi.org/10.1109/sfcs.2001.959917openalex-snapshot
Online facility location
inferredcites →https://doi.org/10.1109/sfcs.2003.1238226openalex-snapshot
Bounded geometries, fractals, and low-distortion embeddings
inferredcites →https://doi.org/10.1109/tit.2009.2021326openalex-snapshot
Random Projection Trees for Vector Quantization
inferredcites →https://doi.org/10.1137/0213014openalex-snapshot
On the Complexity of Some Common Geometric Location Problems
inferredcites →https://doi.org/10.1137/1.9781611975031.29openalex-snapshot
A Fast Approximation Scheme for Low-Dimensional k-Means
inferredcites →https://doi.org/10.1137/s0097539701388884openalex-snapshot
Quick k -Median, k -Center, and Facility Location for Sparse Graphs
inferredcites →https://doi.org/10.1137/s0097539702404055openalex-snapshot
A Nearly Linear-Time Approximation Scheme for the Euclidean k -Median Problem
inferredcites →https://doi.org/10.1137/s0097539704446281openalex-snapshot
Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
inferredcites →https://doi.org/10.1137/s0097539796309764openalex-snapshot
Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k -MST, and Related Problems
inferredcites →https://doi.org/10.1145/1007352.1007399openalex-snapshot
Bypassing the embedding
inferredcites →https://doi.org/10.1145/1132516.1132599openalex-snapshot
Searching dynamic point sets in spaces with bounded doubling dimension
inferredcites →https://doi.org/10.1145/276698.276718openalex-snapshot
Approximation schemes for Euclidean k -medians and related problems
inferredcites →https://doi.org/10.1145/2897518.2897549openalex-snapshot
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
inferredcites →https://doi.org/10.1145/290179.290180openalex-snapshot
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
inferredcites →https://doi.org/10.1145/3188745.3188882openalex-snapshot
Constant approximation for k-median and k-means with outliers via iterative rounding
inferredcites →https://doi.org/10.1145/3301446openalex-snapshot
Approximation Schemes for Clustering with Outliers
inferredcites →https://doi.org/10.1145/513400.513402openalex-snapshot
A local search approximation algorithm for k-means clustering
inferredcites →https://doi.org/10.1145/62212.62255openalex-snapshot
Optimal algorithms for approximate clustering
inferredcites →https://doi.org/10.5555/2133036.2133102openalex-snapshot
Fast, precise and dynamic distance queries
inferredcites →https://doi.org/10.5555/365411.365555openalex-snapshot
Algorithms for facility location problems with outliers

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.2139/ssrn.4724960openalex-extracted
Impossibility of Depth Reduction in Explainable Clustering
inferred← citeshttps://doi.org/10.1007/978-3-031-15914-5_16openalex-snapshot
Generalized $$k$$-Center: Distinguishing Doubling and Highway Dimension
inferred← citeshttps://doi.org/10.1007/978-3-031-39698-4openalex-snapshot
Euro-Par 2023: Parallel Processing
inferred← citeshttps://doi.org/10.1007/978-3-031-39698-4_32openalex-snapshot
Distributed k-Means with Outliers in General Metrics
inferred← citeshttps://doi.org/10.1007/978-981-96-4445-2_27openalex-snapshot
Improved Approximation Algorithm for Individual Fairness k-Median
inferred← citeshttps://doi.org/10.1007/s00453-025-01357-1openalex-snapshot
Generalized $$k$$-Center: Distinguishing Doubling and Highway Dimension
inferred← citeshttps://doi.org/10.1016/j.jpdc.2024.104966openalex-snapshot
MapReduce algorithms for robust center-based clustering in doubling metrics
inferred← citeshttps://doi.org/10.1016/j.tcs.2022.05.014openalex-snapshot
Better guarantees for k-median with service installation costs
inferred← citeshttps://doi.org/10.1016/j.tcs.2026.115900openalex-snapshot
Better guarantees for individual fairness k-median
inferred← citeshttps://doi.org/10.1109/focs.2019.00040openalex-snapshot
Inapproximability of Clustering in Lp Metrics
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00050openalex-snapshot
Streaming Facility Location in High Dimension via Geometric Hashing
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00066openalex-snapshot
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation
inferred← citeshttps://doi.org/10.1109/tnnls.2024.3392211openalex-snapshot
Robust k -Means-Type Clustering for Noisy Data
inferred← citeshttps://doi.org/10.1145/3519935.3519946openalex-snapshot
Towards optimal lower bounds for k-median and k-means coresets
inferred← citeshttps://doi.org/10.1145/3534678.3539409openalex-snapshot
Scalable Differentially Private Clustering via Hierarchically Separated Trees
inferred← citeshttps://doi.org/10.1145/3717823.3718214openalex-snapshot
Near-Optimal Dimension Reduction for Facility Location
inferred← citeshttps://doi.org/10.1145/3798129.3800815openalex-snapshot
Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
inferred← citeshttps://doi.org/10.1145/3798129.3800894openalex-snapshot
A (4+ϵ)-Approximation for Euclidean k-Means via Non-monotone Dual-Fitting
inferred← citeshttps://doi.org/10.1360/ssi-2024-0108openalex-snapshot
A (1+varepsilon)-approximation algorithm for diversity-aware k-median
inferred← citeshttps://doi.org/10.1609/aaai.v38i9.28811openalex-snapshot
Low-Distortion Clustering with Ordinal and Limited Cardinal Information
inferred← citeshttps://doi.org/10.3390/a15020052openalex-snapshot
k-Center Clustering with Outliers in Sliding Windows
inferred← citeshttps://doi.org/10.70675/05aecbe5zbaa6z4121z9719z797e66b4802aopenalex-snapshot
Approximation Algorithms and Sketches for Clustering
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.