Approximation Algorithms for Clustering to Minimize the Sum of Diameters

Keywords

Approximation algorithm, Triangle inequality, Mathematics, Combinatorics, Cluster analysis

References

• Book review: Approximation Algorithms for NP-hard Problems. Edited by Dorit S. Hochbaum (PWS, 1997)Randeep Bhatia, Yoram J. Sussmann — 1998
• Some Geometric Clustering ProblemsUlrich Pferschy, Rüdiger Rudolf, Gerhard J. Woeginger — 1994
• A sublinear time approximation scheme for clustering in metric spacesPiotr Indyk — 1999
• Algorithms for Clustering DataWarren S. Sarle, Anil K. Jain, Richard C. Dubes — 1988
• Clustering to Minimize the Maximum Intercluster DistanceTeofilo F. Gonzalez — 1985
• Approximation Algorithms for NP-Hard ProblemsDorit S. Hochba — 1997
• On Approximate Geometric k -ClusteringJir̆í Matous̆ek — 2000
• Minimum sum of diameters clusteringPierre Hansen, Brigitte Jaumard — 1987
• Cluster analysis and mathematical programmingPierre Hansen, Brigitte Jaumard — 1997
• Computers and Intractability: A Guide to the Theory of NP-CompletenessM. R. Garey, David S. Johnson — 1979
• Optimal Packing and Covering in the Plane are NP-CompleteRobert J. Fowler, Michael S. Paterson, Steven L. Tanimoto — 1981
• Incremental clustering and dynamic information retrievalMoses Charikar, Chandra Chekuri, Tomás Feder — 1997
• Approximation algorithms for projective clusteringPankaj K. Agarwal, Cecilia M. Procopiuc — 2000
• Approximation Algorithms for Min-sum p-clusteringNili Guttmann‐Beck, Refael Hassin — 1998
• Bicriteria Network Design ProblemsMadhav Marathe, R. Ravi, Ravi Sundaram — 1994
• Information retrieval algorithms: a surveyPrabhakar Raghavan — 1997
• A unified approach to approximation algorithms for bottleneck problemsDorit S. Hochbaum, David B. Shmoys — 1986
• An Approximation Algorithm for Clustering Graphs with Dominating Diametral PathJitender S. Deogun, Dieter Kratsch, George Steiner — 1997
• Near-Linear Time Construction of Sparse Neighborhood CoversBaruch Awerbuch, Bonnie Berger, Lenore Cowen — 1999
• The Budgeted Maximum Coverage ProblemSamir Khuller, Anna Moss, Joseph Naor — 1999

Cited by

• Spectral min-max cut for graph partitioning and data clusteringChris Ding, Xiaofeng He, Hongyuan Zha — 2001
• Clusters and covers: geometric set cover algorithmsMatthew Richard Gibson — 2010
• A Framework for Promotion Analysis in Multi-Dimensional SpaceJiawei Han, Tianyi Wu — 2010
• Consensus Algorithms for Trees and StringsJesper Jansson — 2003
• Joint cluster analysis of attribute data and relationship dataRong Ge, Martin Ester, Byron J. Gao — 2008
• On clustering to minimize the sum of radiiMatt Gibson, Gaurav Kanade, Erik Krohn — 2008
• A generalized minimum cost k-clusteringAsaf Levin — 2009
• On Minimum Sum of Radii and Diameters ClusteringBabak Behsaz, Mohammad R. Salavatipour — 2012
• Multi Cover of a Polygon Minimizing the Sum of AreasA. Karim Abu-Affash, Paz Carmi, Matthew J. Katz — 2011
• Clustering to minimize the sum of cluster diametersMoses Charikar, Rina Panigrahy‎ — 2001
• Online Clustering with Variable Sized ClustersJános Csirik, Leah Epstein, Csanád Imreh — 2010
• Efficient Table Anonymization for Aggregate Query AnsweringCecilia M. Procopiuc, Divesh Srivastava — 2009
• Online algorithms for clustering problemsGabriella Divéki — 2014
• CLUSTERING WITH CLUSTER-LEVEL CONSTRAINTSRong Ge — 2008
• A min-max cut algorithm for graph partitioning and data clusteringChris Ding, Xiaofeng He, Hongyuan Zha — 2001
• Approximate Closest Community Search in NetworksXin Huang, Laks V. S. Lakshmanan, Jeffrey Xu Yu — 2015
• Efficient on-line algorithm for maintaining k-cover of sparse bit-stringsAmit Kumar, Preeti Ranjan Panda, Smruti R. Sarangi — 2012
• Approximation Algorithms for Clustering Problems with Lower Bounds and OutliersSara Ahmadian, Chaitanya Swamy — 2016
• Approximation algorithms for clustering problemsBehsaz, Babak — 2012
• Approximation Algorithms for Clustering and Facility Location ProblemsSara Ahmadian — 2017

Related papers

• Clustering to minimize the sum of cluster diametersMoses Charikar, Rina Panigrahy‎ — 2001
• Polynomial time approximation schemes for base station coverage with minimum total radiiNissan Lev-Tov, David Peleg — 2005
• On clustering to minimize the sum of radiiMatt Gibson, Gaurav Kanade, Erik Krohn — 2008
• Minimum-cost coverage of point sets by disksHelmut Alt, Esther M. Arkin, Hervé Brönnimann — 2006
• A Best Possible Heuristic for the k-Center ProblemDorit S. Hochbaum, David B. Shmoys — 1985
• Minimum sum of diameters clusteringPierre Hansen, Brigitte Jaumard — 1987
• Online facility locationAdam Meyerson — 2001