论文标题
恒定因子近似值的上限和上限集群
Constant factor approximations for Lower and Upper bounded Clusterings
论文作者
论文摘要
聚类是机器学习中最根本的问题之一。该领域的研究人员通常需要在集群的大小上进行下限，以保持匿名性和上限，以便于分析。指定最佳集群大小是科学家经常面临的问题。在本文中，我们提出了一个框架，以获得一些突出的聚类目标的恒定因子近似值，并在集群大小上具有下限和上限。这使科学家可以通过指定下部和上限来给出近似的集群大小。我们的结果保留了下限，但可能会稍微违反上限。 ％{grovergd21_lbubfl_cocoon}至$ 2 $。 ％，即$ K $中心（LUKC）和$ K $中位数（LUKM）问题。当两个边界都均匀时，我们研究了问题。我们将框架应用于LUKM及其概括的第一个常数因子近似值，即$ K $ - 易能的位置问题（LUKFL），$β+1 $ 1 $因子违反上限，其中$β$是上限$ k $ - $ - $ - $ -Median和$ k $ - $ -K $ - $ - $ - $ - $ - $ - $ - $ k $ - fiberiality位置问题的上限。我们还对LUKC提出了统一上限的结果，其概括是下限和（均匀）上限$ K $供应商问题（LUKS）。该方法还为上限和上限设施位置问题（LUFL）带来了结果，在Gupta等人造成的上限违反$ 5/2 $的情况下改善了。 当下限和上限之间的差距不太小时，我们还减少了上限的违规行为。
Clustering is one of the most fundamental problem in Machine Learning. Researchers in the field often require a lower bound on the size of the clusters to maintain anonymity and upper bound for the ease of analysis. Specifying an optimal cluster size is a problem often faced by scientists. In this paper, we present a framework to obtain constant factor approximations for some prominent clustering objectives, with lower and upper bounds on cluster size. This enables scientists to give an approximate cluster size by specifying the lower and the upper bounds for it. Our results preserve the lower bounds but may violate the upper bound a little. %{GroverGD21_LBUBFL_Cocoon} to $2$. %namely, $k$ Center (LUkC) and $k$ Median (LUkM) problem. We study the problems when either of the bounds is uniform. We apply our framework to give the first constant factor approximations for LUkM and its generalization, $k$-facility location problem (LUkFL), with $β+1$ factor violation in upper bounds where $β$ is the violation of upper bounds in solutions of upper bounded $k$-median and $k$-facility location problems respectively. We also present a result on LUkC with uniform upper bounds and, its generalization, lower and (uniform) upper bounded $k$ supplier problem (LUkS). The approach also gives a result on lower and upper bounded facility location problem (LUFL), improving upon the upper bound violation of $5/2$ due to Gupta et al. We also reduce the violation in upper bounds for a special case when the gap between the lower and upper bounds is not too small.
