ITR: Collaborative Research: Smoothed Analysis of Algorithms

ITR：协作研究：算法的平滑分析

• 批准号: 0324914
• 负责人: Daniel Spielman
• 金额: $ 50万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-09-01 至 2007-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0324914&HistoricalAwards=false
• 关键词: ITR; Collaborative; Research; Smoothed; Analysis

Graph partitioning is a fundamental combinatorial optimizationproblem that has many practical applications such asin supporting efficient load balancing for parallel processing,in VLSI layout, and in data clustering. This proposed research program focuses on the study of spectral methods for graph partitioning.Spectral methods make use of the eigenvectors of graph matrices (e.g., the Laplacian or the adjacency matrix of a graph) to construct a qualitypartitioning. They have been popularly used in practicefor partitioning meshes in scientific simulation, for dividing graphsderived from circuits, and for clustering data in web-graph analysisand information organization. However, the quality of the partition that these methods should produce has so far eluded precise analysis.Spielman and the PI made some breakthrough progresses.In particular, by proving that the second smallest eigenvalue ofthe Laplacian matrices of bounded-degree planar graphsis at most O(1/n), Spielman and the PIshowed that proper use of spectral techniques can producea bisection of graphs with cut size at most $O(\sqrt{n})$,which is best possible for the family of planar graphs.

图划分是一个基本的组合优化问题，在支持并行处理的高效负载均衡、VLSI布局和数据集群等方面有着广泛的实际应用。谱方法利用图矩阵的特征向量(如图的拉普拉斯矩阵或邻接矩阵)来构造质划分。它们在实际中被广泛用于科学模拟中的网格划分、电路导出的图的划分以及网络图分析和信息组织中的数据聚类。然而，到目前为止，这些方法应该产生的划分的性质一直没有得到精确的分析。Spielman和PI取得了一些突破性的进展。特别是，通过证明有界度平面图的拉普拉斯矩阵的第二小特征值至多O(1/n)，Spielman和PI证明了适当地使用谱技术可以产生割长至多$O(\Sqrt{n})$的平面图的二分图，这对于平面图族是最可能的。