ITR: Collaborative Research: Smoothed Analysis of Algorithms

图划分是一个基本的组合优化问题，有许多实际应用，如支持有效的负载平衡并行处理，在超大规模集成电路布局，并在数据集群。本研究计划的重点是研究用于图划分的谱方法。谱方法利用图矩阵的特征向量（例如，拉普拉斯算子或图的邻接矩阵）来构造质量划分。它们在科学模拟中被广泛用于网格划分，用于电路图的划分，以及用于网络图分析和信息组织中的数据聚类。Spielman和PI取得了一些突破性的进展，特别是通过证明有界度平面图的Laplacian矩阵的次小特征值至多为O（1/n），Spielman和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.