ITR: Collaborative Research: Smoothed Analysis of Algorithms

图划分是一个基本的组合优化问题，有许多实际应用，如支持并行处理的有效负载平衡，VLSI布局和数据聚类。本研究计划的重点是研究图划分的谱方法。谱方法利用图矩阵的特征向量（例如，图的拉普拉斯矩阵或邻接矩阵）来构造一个质量分区。它们在实践中被广泛应用于科学模拟中的网格划分、电路图的划分以及网络图分析和信息组织中的数据聚类。然而，到目前为止，这些方法应该产生的分区的质量还没有得到精确的分析。斯皮尔曼和PI取得了一些突破性进展。特别是，通过证明有界度平面图的拉普拉斯矩阵的第二小特征值不超过O(1/n)， Spielman等人证明了正确使用谱技术可以产生切尺寸不超过$O(\sqrt{n})$的图的平分，这是平面图族的最佳可能。

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.