Reconstructing Many Partitions Using Spectral Techniques
Reconstructing Many Partitions Using Spectral Techniques
复制标题
使用光谱技术重建多个分区
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
D. Mitsche
中科院分区：
文献类型：
--
作者：
Joachim Giesen;D. Mitsche
n项集合的划分是将这些项分组为k个不相交的、大小相等的类。任何分区都可以建模为图。当且仅当相关项属于同一类时，这些项成为图的顶点，两个顶点通过一条边连接。在种植分区模型中，给出一个对分区建模的图，该图被随机噪声遮蔽，即类内的边可以被移除，类间的边可以被插入。任务是根据这个图重建种植分区。在我们研究的模型中，类的数量k控制任务的难度。我们设计了一种谱划分算法，该算法渐近地几乎肯定地重构到$k = csqrt{n}$划分，其中c是一个小常数，在时间Ck poly(n)中，其中c是另一个常数。
A partitioning of a set of n items is a grouping of these items into k disjoint, equally sized classes. Any partition can be modeled as a graph. The items become the vertices of the graph and two vertices are connected by an edge if and only if the associated items belong to the same class. In a planted partition model a graph that models a partition is given, which is obscured by random noise, i.e., edges within a class can get removed and edges between classes can get inserted. The task is to reconstruct the planted partition from this graph. In the model that we study the number k of classes controls the difficulty of the task. We design a spectral partitioning algorithm that asymptotically almost surely reconstructs up to $k = csqrt{n}$ partitions, where c is a small constant, in time Ck poly(n), where C is another constant.