AF: Small: Cuts, Connectivity and Partitioning in Graphs, Hypergraphs and Beyond

AF：小：图、超图及其他领域的切割、连接和分区

• 批准号: 1907937
• 负责人: Karthekeyan Chandrasekaran
• 金额: $ 50万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1907937&HistoricalAwards=false
• 关键词: AF; Small; Cuts; Connectivity; Partitioning

Graphs and networks are ubiquitous in computer science, artificial intelligence, and social sciences. Many real-life applications, such as reliability in communication networks and clustering in social networks, can be modeled as partitioning problems in graphs and related structures. For example, finding the minimum number of base stations in a wireless network whose disruption will disconnect communication between two given agents, and finding groups of people in a social network that have strong ties amongst themselves when compared to outsiders, can both be modeled as partitioning problems. This project aims to design new efficient algorithms for fundamental partitioning problems in structures that generalize graphs. The project will drive the integration of generalized graph models in several courses currently taught by the PIs in Computer Science and Industrial Engineering. Lecture notes from these courses and codes of algorithms developed as part of this project will be made publicly available. The project will support two or more PhD students. The PIs are working with students from under-represented groups and will continue to make efforts to recruit additional graduate and undergraduate students to diversify the population of researchers in theoretical computer science. The PIs plan to organize the Midwest Theory Day at their institution in the near future to bring together a broad cross-section of researchers and students.Cuts, connectivity and partitioning problems in graphs are a central topic in combinatorial optimization and theoretical computer science. While undirected graphs have been extensively studied previously, the primary goal of this project is to address these problems in more complex structures including directed graphs, hypergraphs, and submodular set functions. The complexity status of several problems in these richer models is open. The PIs will investigate polynomial-time solvability, structural results such as sparsification, approximation algorithms, improved running times, and the development of deterministic algorithms where only randomized algorithms are currently known.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.

图和网络在计算机科学、人工智能和社会科学中无处不在。许多现实生活中的应用，例如通信网络中的可靠性和社交网络中的聚类，可以建模为图和相关结构中的分区问题。例如，在无线网络中查找其中断将断开两个给定代理之间的通信的最小基站数量，以及在社交网络中查找与外部人员相比具有很强联系的人群，都可以建模为分区问题。该项目旨在为泛化图结构中的基本划分问题设计新的有效算法。该项目将推动计算机科学和工业工程 PI 目前教授的几门课程中广义图模型的集成。这些课程的讲义和作为该项目一部分开发的算法代码将公开发布。该项目将支持两名或更多博士生。 PI 正在与来自代表性不足群体的学生合作，并将继续努力招募更多的研究生和本科生，以使理论计算机科学研究人员群体多样化。 PI 计划在不久的将来在他们的机构组织中西部理论日，将广泛的研究人员和学生聚集在一起。图中的切割、连通性和分区问题是组合优化和理论计算机科学的中心主题。虽然无向图之前已被广泛研究，但该项目的主要目标是在更复杂的结构中解决这些问题，包括有向图、超图和子模集函数。这些更丰富的模型中的几个问题的复杂性状态是开放的。 PI 将研究多项式时间可解性、稀疏化等结构结果、近似算法、改进的运行时间以及目前仅已知随机算法的确定性算法的开发。该奖项反映了 NSF 的法定使命，并被认为值得通过以下方式获得支持：使用基金会的智力价值和更广泛的影响审查标准进行评估。

项目成果

Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k

计算和枚举固定 k 的超图 k 划分问题的最佳割集

• 发表时间: 2022-01
• 期刊: and Programming (ICALP 2022
• 作者: Beideman, Calvin;Chandrasekaran, Karthekeyan;Wang, Weihang
• 通讯作者: Wang, Weihang

Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

确定性多项式时间内固定 k 的超图 k 割

• DOI: 10.1287/moor.2021.1250
• 发表时间: 2022-01
• 期刊: Mathematics of Operations Research
• 影响因子: 1.7
• 作者: Chandrasekaran, Karthekeyan;Chekuri, Chandra
• 通讯作者: Chekuri, Chandra

Fixed parameter approximation scheme for min-max k-cut

最小-最大 k 割的固定参数近似方案

• 发表时间: 2022-01
• 期刊: Mathematical programming
• 影响因子: 2.7
• 作者: Chandrasekaran, Karthekeyan;Wang, Weihang
• 通讯作者: Wang, Weihang

Min-max Partitioning of Hypergraphs and Symmetric Submodular Functions

超图和对称子模函数的最小-最大划分

• DOI: 10.1137/1.9781611976465.64
• 发表时间: 2021-01
• 期刊: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA
• 作者: Chandrasekaran, Karthekeyan;Chekuri, Chandra
• 通讯作者: Chekuri, Chandra

𝓁_p-Norm Multiway Cut

?_p-范数多路切割

• DOI: 10.4230/lipics.esa.2021.29
• 发表时间: 2021-01
• 期刊: 29th Annual European Symposium on Algorithms (ESA 2021
• 作者: Chandrasekaran, Karthekeyan;Wang, Weihang
• 通讯作者: Wang, Weihang