Online clustering is the process of dynamically partitioning a set of points into clusters in a sequential manner, where points arrive one after another and are assigned to clusters upon arrival. We focus on the one-dimensional clustering scenario, where the cost of a cluster is the unit cost of opening cluster 1 plus the \(\theta \) -th power cost of the cluster diameter. The objective is to minimize the total cost incurred by the algorithm in opening clusters. We investigate both the strict model and the flexible model, both of which maintain two essential properties: points allocated to a given cluster must remain assigned to that cluster, and clusters cannot be merged or split. In the strict model, cluster diameters and precise positions are predetermined during the initialization of clusters. In the flexible model, the algorithm has the flexibility to move or expand clusters, as long as points allocated to a cluster remain assigned to that cluster. This paper introduces the \(GRID_a\) algorithm for the strict model’s online problem and the \(SOSM_a\) algorithm for the semi-online problem, providing proofs of their approximation ratios. For the flexible model’s online problem, we present the \(FGRID_a\) algorithm and establish its approximation ratio.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Online Clustering on the Line with  \(\theta \) -th Power Cost Variable Sized Clustering

  • Rongchuan Luo

摘要

Online clustering is the process of dynamically partitioning a set of points into clusters in a sequential manner, where points arrive one after another and are assigned to clusters upon arrival. We focus on the one-dimensional clustering scenario, where the cost of a cluster is the unit cost of opening cluster 1 plus the \(\theta \) -th power cost of the cluster diameter. The objective is to minimize the total cost incurred by the algorithm in opening clusters. We investigate both the strict model and the flexible model, both of which maintain two essential properties: points allocated to a given cluster must remain assigned to that cluster, and clusters cannot be merged or split. In the strict model, cluster diameters and precise positions are predetermined during the initialization of clusters. In the flexible model, the algorithm has the flexibility to move or expand clusters, as long as points allocated to a cluster remain assigned to that cluster. This paper introduces the \(GRID_a\) algorithm for the strict model’s online problem and the \(SOSM_a\) algorithm for the semi-online problem, providing proofs of their approximation ratios. For the flexible model’s online problem, we present the \(FGRID_a\) algorithm and establish its approximation ratio.