• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions
【24h】

Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions

机译：将Cheeger不等式的算法扩展到较高特征值和分区

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider two generalizations of the problem of finding a sparsest cut in a graph. The first is to find a partition of the vertex set into m parts so as to minimize the sparsity of the partition (defined as the ratio of the weight of edges between parts to the total weight of edges incident to the smallest m - 1 parts). The second is to find a subset of minimum sparsity that contains at most a 1/m fraction of the vertices. Our main results are extensions of Cheeger's classical inequal ity to these problems via higher eigenvalues of the graph. In particu lar, for the sparsest m-partition, we prove that the sparsity is at most 8(1-λ_m)~(1/2) log m where λ_m is the mth largest eigenvalue of the normal ized adjacency matrix. For sparsest small-set, we bound the sparsity by O(1-λ_(m~2) log m)~(1/2).
机译：我们考虑在图中找到最稀疏切口的问题的两种概括。首先是找到一个顶点集合，分为m个部分，以使该部分的稀疏性最小化（定义为部分之间的边的权重与入射到最小m-1个部分的边的总权重之比） 。第二个是找到最小稀疏度的子集，该子集最多包含顶点的1 / m分数。我们的主要结果是通过图的较高特征值将Cheeger的经典不等式扩展到这些问题。特别是，对于最稀疏的m分区，我们证明稀疏度最多为8（1-λ_m）〜（1/2）log m，其中λ_m是正规化邻接矩阵的第m个最大特征值。对于最稀疏的小集，我们将稀疏度限制为O（1-λ_（m〜2）log m）〜（1/2）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号