ITR: Collaborative Research: Smoothed Analysis of Algorithms

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