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布局和数据群集中。该提出的研究计划着重于用于图形分区的光谱方法的研究。光谱方法利用图矩阵的特征向量（例如，laplacian或图形的邻接矩阵）来构建质量分配。它们已被广泛用于在科学模拟中分区网格的实践中，用于将绘制的图表与电路划分，以及在Web-Graph分析和信息组织中将数据划分。 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}）$，对于平面图的家族来说，这是最好的。