Exact and approximation algorithms for clustering

DOI10.1007/S00453-001-0110-YzbMATH Open0994.68178OpenAlexW3137423196MaRDI QIDQ1601015FDOQ1601015

Authors: Pankaj K. Agarwal, Cecilia M. Procopiuc 

Publication date: 17 June 2002

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-001-0110-y

Recommendations

• scientific article; zbMATH DE number 1303609
• Approximation schemes for clustering problems
• scientific article; zbMATH DE number 1629976
• An approximation algorithm for a problem of cluster analysis
• Approximation algorithms for stochastic clustering
• scientific article; zbMATH DE number 1882434
• Approximate algorithms for graph clustering problem
• Approximation algorithms for clustering problems with lower bounds and outliers
• Efficient approximation algorithms for clustering point-sets

zbMATH Keywords

\(k\)-center problem

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Cited In (72)

• Title not available (Why is that?)
• Clustering mixtures with almost optimal separation in polynomial time
• Parameterized approximation algorithms and lower bounds for \(k\)-center clustering and variants
• The k-centre problem for classes of cyclic words
• Efficient \(k\)-center algorithms for planar points in convex position
• Clustering with faulty centers
• Tight lower bounds for approximate \& exact \(k\)-center in \(\mathbb{R}^d\)
• Sublinear‐time approximation algorithms for clustering via random sampling
• Covering a set of line segments with a few squares
• Bichromatic 2-center of pairs of points
• Title not available (Why is that?)
• An improved approximation algorithm for the most points covering problem
• Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs
• Randomized Algorithm of Finding the True Number of Clusters Based on Chebychev Polynomial Approximation
• Covering convex polygons by two congruent disks
• Covering convex polygons by two congruent disks
• Covering many or few points with unit disks
• An algorithmic framework for solving geometric covering problems -- with applications
• Fair colorful \(k\)-center clustering
• An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes
• FINDING PLANAR REGIONS IN A TERRAIN – IN PRACTICE AND WITH A GUARANTEE
• Linear-size universal discretization of geometric center-based problems in fixed dimensions
• Efficient approximation algorithms for clustering point-sets
• Title not available (Why is that?)
• The parameterized hardness of the \(k\)-center problem in transportation networks
• Exact algorithms for size constrained 2-clustering in the plane
• Near-linear time approximation schemes for geometric maximum coverage
• Title not available (Why is that?)
• Linear-time approximation schemes for clustering problems in any dimensions
• THE ALIGNED K-CENTER PROBLEM
• Unit disk cover problem in 2D
• Approximation algorithms for the \(k\)-center problem: an experimental evaluation
• Constrained \(k\)-center problem on a convex polygon
• Approximation algorithms for the metric maximum clustering problem with given cluster sizes.
• On the discrete unit disk cover problem
• Preclustering algorithms for imprecise points
• Approximate Clustering with Same-Cluster Queries
• Faster algorithms for the constrained \(k\)-means problem
• Evaluation of a Branch and Bound Algorithm for Clustering
• Faster algorithms for the constrained \(k\)-means problem
• The Euclidean \(k\)-supplier problem in \(I R^2\)
• On capacitated covering with unit balls
• Polynomial time approximation schemes for all 1-center problems on metric rational set similarities
• Clustering via the modified Petford-Welsh algorithm
• A simple linear algorithm for computing rectilinear 3-centers
• Lagrangean duals and exact solution to the capacitated \(p\)-center problem
• Deterministic \(o(1)\)-approximation algorithms to 1-center clustering with outliers
• An efficient algorithm for the proximity connected two center problem
• Theory and application of width bounded geometric separators
• On the discrete unit disk cover problem
• Approximate range queries for clustering
• Range-clustering queries
• Aggregation error for location models: Survey and analysis
• The computational complexity and approximability of a series of geometric covering problems
• Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions
• Clustering motion
• The 2-center problem in three dimensions
• A New Composite Algorithm for Clustering Problems
• Graph clustering
• Heuristic methods for large centroid clustering problems
• Title not available (Why is that?)
• Computing \(k\) centers over streaming data for small \(k\)
• Title not available (Why is that?)
• On interval and circular-arc covering problems
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• The Complete Gradient Clustering Algorithm: properties in practical applications
• Approximation algorithms for projective clustering
• A PTAS for the cardinality constrained covering with unit balls
• Covering a set of line segments with a few squares
• Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs
• The parameterized hardness of the \(k\)-center problem in transportation networks
• The within-strip discrete unit disk cover problem

This page was built for publication: Exact and approximation algorithms for clustering

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