Polynomial time approximation schemes for geometric k-clustering

No abstract is available for this paper.

• Publication year

  2000

• Venue

  Proceedings 41st Annual Symposium on Foundations of Computer Science

• Publication date

  2000-11-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SFCS.2000.892123
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Probabilistic Method

  2015cited by this paper
• The Genomics Revolution and its Challenges for Algorithmic Research

  2000cited by this paper
• Clustering for edge-cost minimization (extended abstract)

  2000cited by this paper
• Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces

  1999cited by this paper
• Authoritative sources in a hyperlinked environment

  1999cited by this paper
• Clustering in large graphs and matrices

  1999cited by this paper
• A constant-factor approximation algorithm for the k-median problem (extended abstract)

  1999cited by this paper
• Primal-dual approximation algorithms for metric facility location and k-median problems

  1999cited by this paper
• Improved combinatorial algorithms for the facility location and k-median problems

  1999cited by this paper
• On Two Segmentation Problems

  1999influential reference
• Learning mixtures of Gaussians

  1999cited by this paper
• A sublinear time approximation scheme for clustering in metric spaces

  1999cited by this paper
• Fast hierarchical clustering and other applications of dynamic closest pairs

  1999cited by this paper
• Efficient algorithms for geometric optimization

  1998cited by this paper
• Fast Monte-Carlo algorithms for finding low-rank approximations

  1998cited by this paper
• Authoritative Soueces in a Hyper-linked Environment

  1998cited by this paper
• Approximation schemes for Euclidean k-medians and related problems

  1998cited by this paper
• Greedy strikes back: improved facility location algorithms

  1998cited by this paper
• The Probabilistic Method

  1998cited by this paper
• E cient Algorithms for Geometric Optimization

  1998influential reference
• A randomized approximation scheme for metric MAX-CUT

  1998cited by this paper
• Efficient search for approximate nearest neighbor in high dimensional spaces

  1998cited by this paper
• Syntactic Clustering of the Web

  1997cited by this paper
• Exact and Approximation Algortihms for Clustering

  1997cited by this paper
• Two algorithms for nearest-neighbor search in high dimensions

  1997cited by this paper
• The regularity lemma and approximation schemes for dense problems

  1996cited by this paper
• Approximation algorithms for geometric problems

  1996cited by this paper
• Using Linear Algebra for Intelligent Information Retrieval

  1995cited by this paper
• Polynomial time approximation schemes for dense instances of NP-hard problems

  1995cited by this paper
• The geometry of graphs and some of its algorithmic applications

  1994cited by this paper
• Constant interaction-time scatter/gather browsing of very large document collections

  1993cited by this paper
• Scatter/Gather: a cluster-based approach to browsing large document collections

  1992cited by this paper
• Improving the retrieval of information from external sources

  1991cited by this paper
• Using latent semantic analysis to improve information retrieval

  1988cited by this paper
• Using latent semantic analysis to improve access to textual information

  1988cited by this paper
• The Johnson-Lindenstrauss lemma and the sphericity of some graphs

  1987cited by this paper
• Extensions of Lipschitz mappings into Hilbert space

  1984cited by this paper
• Pattern recognition

  1974cited by this paper

• Clustering Permutations: New Techniques with Streaming Applications

  2022cites this paper
• Coevolutive clustering algorithm for large datasets

  2020cites this paper
• Ανάπτυξη και βελτίωση μεθόδων απλοποίησης νέφους σημείων

  2019cites this paper
• Approximate nearest neighbor search for ℓp-spaces (2

  2019cites this paper
• Adaptive Simulated Evolution based Approach for Cluster Optimization in Wireless Sensor Networks

  2018cites this paper
• Approximate Nearest Neighbor Search for \ell _p -Spaces (2 via Embeddings

  2018cites this paper
• Algorithmic Results for Clustering and Refined Physarum Analysis

  2018cites this paper
• Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015, Kingston, Ontario, Canada, August 10-12, 2015

  2015cites this paper
• Dimension reduction techniques for ℓp, 1 ≤ p < ∞, with applications

  2014cites this paper
• Computational Prediction of Gene Functions through Machine Learning methods and Multiple Validation Procedures

  2014cites this paper
• Approximation and Streaming Algorithms for Projective Clustering via Random Projections

  2014cites this paper
• Algorithmes auto-stabilisants pour la construction de structures couvrantes réparties. (Self-Stabilizing Algorithms for Constructing Distributed Spanning Structures)

  2013cites this paper
• Self Organized Biogeography Algorithm for Clustering

  2013cites this paper
• Clustering Affine Subspaces: Hardness and Algorithms

  2013cites this paper
• Approximation Algorithms and New Models for Clustering and Learning

  2013cites this paper
• Beyond Worst-Case Analysis in Privacy and Clustering: Exploiting Explicit and Implicit Assumptions

  2013cites this paper
• Complexity Issues on PTAS

  2013cites this paper
• A novel cooperative algorithm for clustering large databases using sampling

  2012cites this paper
• Improved Spectral-Norm Bounds for Clustering

  2012cites this paper
• Clustering Affine Subspaces : Algorithms and Hardness Thesis

  2012cites this paper
• Anomaly Base Network Intrusion Detection by Using Random Decision Tree and Random Projection: A Fast Network Intrusion Detection Technique

  2011cites this paper
• Deterministic Feature Selection for K-Means Clustering

  2011influential citation
• Randomized Dimensionality Reduction for $k$ -Means Clustering

  2011cites this paper
• Stochastic Dimensionality Reduction for K-means Clustering

  2011cites this paper
• Topics in Matrix Sampling Algorithms

  2011cites this paper
• Constrained Minimum-k-Star Clustering and its application to the consolidation of farmland

  2011cites this paper
• Proposal : Approximation Algorithms and New Models for Clustering and Learning

  2011cites this paper
• The delay-constrained information coverage problem in mobile sensor networks: single hop case

  2010cites this paper
• The Base Station Placement for Delay-Constrained Information Coverage in Mobile Wireless Networks

  2010cites this paper
• Stability Yields a PTAS for k-Median and k-Means Clustering

  2010cites this paper
• Spectral Algorithms

  2009cites this paper
• Image-mapped data clustering: An efficient technique for clustering large data sets

  2008cites this paper
• Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning

  2008cites this paper
• IMDC: An Image-Mapped Data Clustering Technique for Large Datasets

  2007cites this paper
• Coresets for Discrete Integration and Clustering

  2006cites this paper
• On the Optimality of the Dimensionality Reduction Method

  2006cites this paper
• 1 Adaptive Mean Shift Based Clustering in High Dimensions

  2006cites this paper
• Design and Test of Object Aligning Grippers for Industrial Applications

  2006cites this paper
• Self-improving algorithms

  2006influential citation
• Clustering via matrix powering

  2004cites this paper
• Computational Problems in Noisy SNP and Haplotype Analysis: Block Scores, Block Identification, and Population Stratification

  2004cites this paper
• Clustering Large Graphs via the Singular Value Decomposition

  2004cites this paper
• On the impossibility of dimension reduction in l1

  2003cites this paper
• On the Impossibility of Dimension Reduction in l1

  2003cites this paper
• On Finding Large Conjunctive Clusters

  2003cites this paper
• On the impossibility of dimension reduction in /spl lscr//sub 1/

  2003cites this paper
• Techniques for Clustering Massive Data Sets

  2003cites this paper
• Clustering in High Dimensions

  2003influential citation
• Mean shift based clustering in high dimensions: a texture classification example

  2003cites this paper
• Clustering Data Streams: Theory and Practice

  2003cites this paper
• Approximate clustering via core-sets

  2002influential citation
• Dimension Reduction in the l 1 norm

  2002cites this paper
• Dimension reduction in the /spl lscr//sub 1/ norm

  2002cites this paper
• Algorithmic applications of low-distortion geometric embeddings

  2001cites this paper
• Randomized Algorithms for Geometric Optimization Problems

  2001cites this paper
• Random projection in dimensionality reduction: applications to image and text data

  2001cites this paper
• ec 2 01 5 Dimension reduction techniques for l p ( 1 ≤ p ≤ 2 ) , with applications

  year unknowncites this paper