Optimal algorithms for approximate clustering

No abstract is available for this paper.

• Publication year

  1988

• Venue

  Symposium on the Theory of Computing

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/62212.62255
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Fast algorithms for vector quantization picture coding

  1987cited by this paper
• A unified approach to approximation algorithms for bottleneck problems

  1986cited by this paper
• An optimal algorithm for the all-nearest-neighbors problem

  1986cited by this paper
• Computational Geometry

  1985cited by this paper
• A Best Possible Heuristic for the k-Center Problem

  1985cited by this paper
• Clustering to Minimize the Maximum Intercluster Distance

  1985cited by this paper
• Vector quantization

  1984cited by this paper
• On the Complexity of Some Common Geometric Location Problems

  1984cited by this paper
• Lower bounds for algebraic computation trees

  1983cited by this paper
• Approximation algorithms for NP-complete problems on planar graphs

  1983cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• Optimal Packing and Covering in the Plane are NP-Complete

  1981cited by this paper
• Easy and hard bottleneck location problems

  1979cited by this paper
• On the Complexity of Clustering Problems

  1978cited by this paper
• The Rectilinear Steiner Tree Problem is NP Complete

  1977cited by this paper

• On Small Pair Decompositions for Point Sets

  2026cites this paper
• Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond

  2025influential citation
• Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering

  2025cites this paper
• On Tight FPT Time Approximation Algorithms for k-Clustering Problems

  2025cites this paper
• Beyond 2-Approximation for k-Center in Graphs

  2025cites this paper
• Clustering Point Sets Revisited

  2025influential citation
• Binary k-Center with Missing Entries: Structure Leads to Tractability

  2025cites this paper
• Approximate all-pairs Hamming distances and 0-1 matrix multiplication

  2025cites this paper
• Fast approximate ℓ-center clustering in high dimensional spaces

  2025cites this paper
• Faster Approximation Algorithms for k-Center via Data Reduction

  2025cites this paper
• Gaussian processes for dynamics learning in model predictive control

  2025cites this paper
• Multiplication of 0-1 matrices via clustering

  2025cites this paper
• Clustering with Set Outliers and Applications in Relational Clustering

  2025cites this paper
• A new model and DCA based algorithm for clustering

  2025cites this paper
• Parameterized Approximation Algorithms and Lower Bounds for k-Center Clustering and Variants

  2024influential citation
• Computing A Well-Representative Summary of Conjunctive Query Results

  2024cites this paper
• Faster Algorithms for Fair Max-Min Diversification in Rd

  2024cites this paper
• Algorithms for Halfplane Coverage and Related Problems

  2024cites this paper
• On Line-Separable Weighted Unit-Disk Coverage and Related Problems

  2024cites this paper
• Resilient k-Clustering

  2024cites this paper
• From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem

  2024cites this paper
• lpNTK: Better Generalisation with Less Data via Sample Interaction During Learning

  2024cites this paper
• SEED: Domain-Specific Data Curation With Large Language Models

  2023cites this paper
• A Fast Coherent Point Drift Method for Rigid 3D Point Cloud Registration

  2023cites this paper
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces

  2023cites this paper
• Finding a Cluster in Incomplete Data

  2023cites this paper
• Geometric Hitting Set for Line-Constrained Disks and Related Problems

  2023cites this paper
• Impossibility of Depth Reduction in Explainable Clustering

  2023cites this paper
• Forty years of color quantization: a modern, algorithmic survey

  2023cites this paper
• Dynamic algorithms for k-center on graphs

  2023cites this paper
• On the Line-Separable Unit-Disk Coverage and Related Problems

  2023cites this paper
• On the parameterized complexity of clustering problems for incomplete data

  2023cites this paper
• Fully Dynamic Consistent k-Center Clustering

  2023cites this paper
• Fully Dynamic k-Center in Low Dimensions via Approximate Furthest Neighbors

  2023cites this paper
• Inapproximability of Maximum Diameter Clustering for Few Clusters

  2023influential citation
• Clustering with Faulty Centers

  2023influential citation
• Minimizing the Size of the Uncertainty Regions for Centers of Moving Entities

  2023cites this paper
• SEED: Simple, Efficient, and Effective Data Management via Large Language Models

  2023cites this paper
• k-Center Clustering with Outliers in the MPC and Streaming Model

  2023cites this paper
• Sample Relationships through the Lens of Learning Dynamics with Label Information

  2022cites this paper
• An Optimal Transport Approach for Selecting a Representative Subsample with Application in Efficient Kernel Density Estimation

  2022cites this paper
• The incremental online k-means clustering algorithm and its application to color quantization

  2022influential citation
• Hierarchy cost of hierarchical clusterings

  2022cites this paper
• A Framework and Benchmark for Deep Batch Active Learning for Regression

  2022influential citation
• Adaptively Partitioning Max-Affine Estimators for Convex Regression

  2022cites this paper
• Generalized \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-Center: Distinguishing Doubling and High

  2022cites this paper
• Sampling Algorithms for Unsupervised Prototype Selection

  2022cites this paper
• Optimal clustering by merge-based branch-and-bound

  2022cites this paper
• Sublinear time algorithms for greedy selection in high dimensions

  2022cites this paper
• Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space

  2021cites this paper
• On Some Variants of Euclidean K-Supplier

  2021cites this paper
• Improved approximation algorithms for two Euclidean k-Center variants

  2021cites this paper
• Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model

  2021influential citation
• Improvements on approximation algorithms for clustering probabilistic data

  2021cites this paper
• Coresets for k-median clustering under Fréchet and Hausdorff distances

  2021cites this paper
• Covering Convex Polygons by Two Congruent Disks

  2021cites this paper
• Algorithms for the Line-Constrained Disk Coverage and Related Problems

  2021cites this paper
• Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints

  2021cites this paper
• Differentially Private Algorithms for Clustering with Stability Assumptions

  2021influential citation
• Parameterized Approximation Algorithms for k-Center Clustering and Variants

  2021influential citation
• Sensor Placement for Globally Optimal Coverage of 3D-Embedded Surfaces

  2021cites this paper
• Approximability of the dispersed p→-neighbor k-supplier problem

  2021cites this paper
• Optimal Fully Dynamic k-Centers Clustering

  2021cites this paper
• Clustering with Neighborhoods

  2021cites this paper
• The Parameterized Complexity of Clustering Incomplete Data

  2021cites this paper
• FPT Approximation for Fair Minimum-Load Clustering

  2021cites this paper
• On fully dynamic constant-factor approximation algorithms for clustering problems

  2021cites this paper
• Optimally Guarding Perimeters and Regions with Mobile Range Sensors

  2020influential citation
• An O(log⁡n) query time algorithm for reducing ϵ-NN to (c, r)-NN

  2020cites this paper
• k-Median clustering under discrete Fréchet and Hausdorff distances

  2020cites this paper
• New Directions in Streaming Algorithms

  2020cites this paper
• Computing Euclidean k-Center over Sliding Windows

  2020influential citation
• Approximation algorithms for probabilistic $k$-center clustering

  2020cites this paper
• Formal methods approach to the charging facility location problem for battery electric vehicles

  2020cites this paper
• Clustering under Perturbation Stability in Near-Linear Time

  2020cites this paper
• Leveraging Model Flexibility and Deep Structure: Non-Parametric and Deep Models for Computer Vision Processes with Applications to Deep Model Compression

  2020cites this paper
• Greedy <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-Center From Noisy Distance Samples

  2020cites this paper
• Clustering Moving Entities in Euclidean Space

  2020cites this paper
• W[1]-hardness of the k-center problem parameterized by the skeleton dimension

  2020cites this paper
• Stateless Information Dissemination Algorithms

  2020cites this paper
• Structural Information and Communication Complexity: 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29–July 1, 2020, Proceedings

  2020cites this paper
• Efficient Indexes for Diverse Top-k Range Queries

  2020cites this paper
• Classification and approximation of geometric location problems (Klassifikation und Approximation von Problemen der Geometrischen Platzierung)

  2019cites this paper
• Image Annotation as Text-Image Matching: Challenge Design and Results

  2019cites this paper
• Putting ridesharing to the test: efficient and scalable solutions and the power of dynamic vehicle relocation

  2019cites this paper
• Digging deeper into clustering and covering problems

  2019cites this paper
• Approximation algorithms III

  2019cites this paper
• Tree-Sliced Approximation of Wasserstein Distances

  2019cites this paper
• An adaptive probabilistic algorithm for online k-center clustering

  2019cites this paper
• Fully dynamic hierarchical diameter k-clustering and k-center

  2019cites this paper
• Fully Dynamic k-Center Clustering in Doubling Metrics

  2019cites this paper
• A Constant Approximation for Colorful k-Center

  2019cites this paper
• A Composable Coreset for k-Center in Doubling Metrics

  2019cites this paper
• Distributed Unit Clustering

  2019cites this paper
• On the hardness of computing an average curve

  2019cites this paper
• Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics

  2019influential citation
• Hierarchy of Transportation Network Parameters and Hardness Results

  2019cites this paper
• Approximating Distance Measures for the Skyline

  2019cites this paper
• Flow-based Alignment Approaches for Probability Measures in Different Spaces

  2019cites this paper
• Dim Sum: Light Clock Tree by Small Diameter Sum

  2019cites this paper