AF: Small: New Challenges and Approaches in Clustering Algorithms

聚类是将数据集划分为相似组的任务，是一种经常应用于计算机科学和其他学科的基本数据分析技术。通常，将任务建模为计算问题，并设计算法以执行任务。该项目研究了公平聚类模型，这对计算和社会至关重要，它可以以公正或公平的方式训练机器学习系统，用于每个受保护群体（基于敏感特征，例如性别）。然而，设计具有公平聚类的可证明保证的算法一直令人沮丧，因为公平版本提出了新的挑战。特别是，用于解决常规（或香草）聚类问题的经典技术在处理公平版本时已经不足。因此，该项目旨在弥合理解和设计工具和技术的差距，以实现与香草集群相匹配的保证。此外，该项目支持研究生的研究和外展活动，以提高当地学校/大学生对理论计算机科学正在进行的研究的认识。这个项目强调了一系列基本的公平聚类问题与公平的平衡概念。这个概念要求每个保护组在每个集群中都有很好的表示。平衡聚类是近年来最流行但也是最困难的聚类模型之一。例如，众所周知，k-median（或k-means）聚类允许多项式时间常数因子近似算法，但对于平衡版本却不知道类似的近似。这个项目研究了近似领域的一般技术的局限性和适用性，比如松弛和圆划分和度量划分。作为该项目的一部分，将设计新的工具和技术，以帮助解决更广泛的问题。该研究还将检查诸如时间复杂性，近似保证和公平满意程度等数量之间的权衡。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Clustering is the task of dividing a dataset into similar groups, a fundamental data analysis technique frequently applied in computer science and other disciplines. Typically, the task is modeled as a computational problem and algorithms are designed in order to perform the task. This project investigates fair clustering models, essential for computing and society, that can train machine learning systems in an unbiased or fair manner for each protected group (defined based on a sensitive feature, say gender). However, designing algorithms with provable guarantees for fair clustering has been frustrating, as the fair versions pose novel challenges. In particular, the classic techniques that have been used to solve regular (or vanilla) clustering problems have fallen short in handling the fair versions. Accordingly, the project aims to bridge this gap of understanding and design tools and techniques to achieve guarantees matching those of vanilla clustering. Additionally, the project supports research by graduate students and outreach activities to create awareness among local school/college students about ongoing research in Theoretical Computer Science. This project highlights a collection of fundamental fair clustering problems with the fairness notion of balance. This notion requires that each protected group is well-represented in every cluster. Balanced clustering has emerged as one of the most popular, but difficult clustering models in recent times. For example, it is widely known that k-median (or k-means) clustering admits polynomial-time constant-factor approximation algorithms, but a similar approximation is not known for the balanced versions. This project investigates the limitations and applicability of generic techniques from the area of approximation, such as relax-and-round and metric partitioning. As a part of the project, new tools and techniques will be designed that would help solve a broader class of problems. The study will also examine the trade-offs between quantities such as time complexity, approximation guarantee, and the extent of fairness satisfaction.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.