AF: Small: New Challenges and Approaches in Clustering Algorithms
AF:小:聚类算法的新挑战和方法
基本信息
- 批准号:2311397
- 负责人:
- 金额:$ 16.3万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2023
- 资助国家:美国
- 起止时间:2023-05-01 至 2026-04-30
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
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.
聚类是将数据集划分为相似组的任务,这是计算机科学和其他学科中经常应用的基本数据分析技术。通常,任务被建模为计算问题,并且算法被设计为执行任务。该项目研究公平聚类模型,这对计算和社会至关重要,可以为每个受保护的群体(基于敏感特征定义,例如性别)以公正或公平的方式训练机器学习系统。然而,设计算法与公平聚类的可证明的保证一直令人沮丧,因为公平的版本提出了新的挑战。特别是,用于解决常规(或普通)聚类问题的经典技术在处理公平版本时已经失败。因此,该项目旨在弥合理解和设计工具和技术的差距,以实现与香草集群相匹配的保证。此外,该项目还支持研究生的研究和推广活动,以提高当地学校/大学生对理论计算机科学正在进行的研究的认识。这个项目强调了一系列基本的公平聚类问题,以及平衡的公平性概念。这个概念要求每个保护组在每个集群中都有良好的表示。平衡聚类是近年来最流行但最困难的聚类模型之一。例如,众所周知,k-中值(或k-均值)聚类允许多项式时间常数因子近似算法,但平衡版本的类似近似是未知的。这个项目研究了近似领域中通用技术的局限性和适用性,例如松弛和舍入以及度量分区。作为该项目的一部分,将设计新的工具和技术,以帮助解决更广泛的问题。该研究还将考察时间复杂性、近似保证和公平性满意度等数量之间的权衡。该奖项反映了NSF的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Sayan Bandyapadhyay其他文献
Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames
矩形和L框交图上的近似支配集
- DOI:
10.4230/lipics.mfcs.2018.37 - 发表时间:
2018 - 期刊:
- 影响因子:0
- 作者:
Sayan Bandyapadhyay;A. Maheshwari;S. Mehrabi;S. Suri - 通讯作者:
S. Suri
Parameterized Approximation Algorithms and Lower Bounds for k-Center Clustering and Variants
k-中心聚类和变体的参数化近似算法和下界
- DOI:
- 发表时间:
2024 - 期刊:
- 影响因子:1.1
- 作者:
Sayan Bandyapadhyay;Zachary Friggstad;Ramin Mousavi - 通讯作者:
Ramin Mousavi
Socially Fair Matching: Exact and Approximation Algorithms
社会公平匹配:精确算法和近似算法
- DOI:
- 发表时间:
2023 - 期刊:
- 影响因子:0
- 作者:
Sayan Bandyapadhyay;F. Fomin;Tanmay Inamdar;Fahad Panolan;Kirill Simonov - 通讯作者:
Kirill Simonov
Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane
平面上多对多点匹配的精确和近似算法
- DOI:
10.4230/lipics.isaac.2021.44 - 发表时间:
2021 - 期刊:
- 影响因子:0
- 作者:
Sayan Bandyapadhyay;A. Maheshwari;M. Smid - 通讯作者:
M. Smid
Near-Optimal Clustering in the k-machine model
k 机模型中的近最优聚类
- DOI:
- 发表时间:
2017 - 期刊:
- 影响因子:0
- 作者:
Sayan Bandyapadhyay;Tanmay Inamdar;Shreyas Pai;Sriram V. Pemmaraju - 通讯作者:
Sriram V. Pemmaraju
Sayan Bandyapadhyay的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342244 - 财政年份:2024
- 资助金额:
$ 16.3万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
- 批准号:
2402572 - 财政年份:2024
- 资助金额:
$ 16.3万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342245 - 财政年份:2024
- 资助金额:
$ 16.3万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Connections between Optimization and Property Testing
合作研究:AF:小型:优化和性能测试之间的新联系
- 批准号:
2402571 - 财政年份:2024
- 资助金额:
$ 16.3万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Directions and Approaches in Discrepancy Theory
合作研究:AF:小:差异理论的新方向和方法
- 批准号:
2327010 - 财政年份:2023
- 资助金额:
$ 16.3万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Directions and Approaches in Discrepancy Theory
合作研究:AF:小:差异理论的新方向和方法
- 批准号:
2327011 - 财政年份:2023
- 资助金额:
$ 16.3万 - 项目类别:
Standard Grant
NSF-BSF: AF: Small: New directions in geometric traversal theory
NSF-BSF:AF:小:几何遍历理论的新方向
- 批准号:
2317241 - 财政年份:2023
- 资助金额:
$ 16.3万 - 项目类别:
Standard Grant
AF: Small: New Tools to Analyze Random Walks
AF:小:分析随机游走的新工具
- 批准号:
2203541 - 财政年份:2022
- 资助金额:
$ 16.3万 - 项目类别:
Standard Grant
AF: Small: Towards New Relaxations for Online Algorithms
AF:小:在线算法的新放松
- 批准号:
2224718 - 财政年份:2022
- 资助金额:
$ 16.3万 - 项目类别:
Standard Grant
AF: Small: New Techniques for Optimal Bounds on MCMC Algorithms
AF:小:MCMC 算法最优边界的新技术
- 批准号:
2147094 - 财政年份:2022
- 资助金额:
$ 16.3万 - 项目类别:
Standard Grant