Balanced k-Center Clustering When k Is A Constant

The problem of constrained $k$-center clustering has attracted significant attention in the past decades. In this paper, we study balanced $k$-center cluster where the size of each cluster is constrained by the given lower and upper bounds. The problem is motivated by the applications in processing and analyzing large-scale data in high dimension. We provide a simple nearly linear time $4$-approximation algorithm when the number of clusters $k$ is assumed to be a constant. Comparing with existing method, our algorithm improves the approximation ratio and significantly reduces the time complexity. Moreover, our result can be easily extended to any metric space.

• Publication year

  2017

• Venue

  Canadian Conference on Computational Geometry

• Publication date

  2017-04-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1704.02515
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Capacitated Center Problems with Two-Sided Bounds and Outliers

  2017cited by this paper
• Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers

  2016cited by this paper
• Distributed Balanced Partitioning via Linear Embedding

  2015cited by this paper
• Data Driven Resource Allocation for Distributed Learning

  2015cited by this paper
• Constant Factor Approximation for Capacitated k-Center with Outliers

  2014cited by this paper
• Centrality of trees for capacitated k\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

  2014cited by this paper
• Distributed Balanced Clustering via Mapping Coresets

  2014cited by this paper
• Centrality of Trees for Capacitated k-Center

  2013cited by this paper
• Fast Clustering with Lower Bounds: No Customer too Far, No Shop too Small

  2013cited by this paper
• Max flows in O(nm) time, or better

  2013cited by this paper
• LP Rounding for k-Centers with Non-uniform Hard Capacities

  2012cited by this paper
• Achieving anonymity via clustering

  2006cited by this paper
• The Capacitated K-Center Problem

  2000cited by this paper
• How to Allocate Network Centers

  1993cited by this paper
• Finding Groups in Data: An Introduction to Cluster Analysis

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

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

  1985cited by this paper

• Capacitated Clustering Problem

  2024cites this paper
• Flexible MEO Down-Link Beamforming Using Constrained Clustering for Near-Optimal Load-Balancing

  2024cites this paper
• Tight FPT Approximation for Constrained k-Center and k-Supplier

  2021cites this paper
• Improved Algorithms for Distributed Balanced Clustering

  2020cites this paper
• SNP selection based on k-center algorithm

  2019cites this paper
• Faster Balanced Clusterings in High Dimension

  2018cites this paper
• В ТЕХНИЧЕСКИХ СИСТЕМАХ О задаче кластеризации с оптимизацией связей элементов кластеров

  year unknowncites this paper