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将研究多项式时间的可解性、稀疏化等结构性结果、近似算法、改进的运行时间以及确定性算法的开发（目前只知道随机算法）。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

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

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

Odd Multiway Cut in Directed Acyclic Graphs

有向无环图中的奇多路割

• DOI: 10.1137/18m1176087
• 发表时间: 2020
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Chandrasekaran, Karthekeyan;Mnich, Matthias;Mozaffari, Sahand
• 通讯作者: Mozaffari, Sahand

?_p-Norm Multiway Cut

?_p-范数多路切割

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

Approximate minimum cuts and their enumeration

近似最小割集及其枚举

• 发表时间: 2023
• 期刊: Symposium on Simplicity in Algorithms (SOSA 2023
• 作者: Beideman, Calvin;Chandrasekaran, Karthekeyan;Wang, Weihang
• 通讯作者: Wang, Weihang

Hypergraph k-cut in randomized polynomial time

• DOI: 10.1007/s10107-019-01443-7
• 发表时间: 2018-01
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Karthekeyan Chandrasekaran;Chao Xu;Xilin Yu