Approximation Algorithm for Sparsest k-Partitioning

Approximation Algorithm for Sparsest k-Partitioning
复制标题

最稀疏 k 划分的近似算法

DOI：
--
复制
发表时间：
2013
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
通讯作者：
K. Makarychev
K. Makarychev
中科院分区：
--
文献类型：
--
作者：
Anand Louis;K. Makarychev

文献摘要

被引文献

相似文献

给定图G，最稀少的切割问题要求找到一组顶点S，该顶点S的扩展最少为 [方程] 其中w是子集的总边缘重量。在这里，我们研究了此问题的自然概括：给定整数k，计算顶点集的k部分{p1，...，pk}，以最小化 [方程] 我们的主要结果是一种多项式时间双标准近似算法，该算法输出了顶点集的A（1- E）k部分，使得每一部分最多都有[方程式]时的扩展。我们还研究了这个问题的平衡版本。
Given a graph G, the sparsest-cut problem asks to find the set of vertices S which has the least expansion defined as [EQUATION] where w is the total edge weight of a subset. Here we study the natural generalization of this problem: given an integer k, compute a k-partition {P1, ..., Pk} of the vertex set so as to minimize [EQUATION] Our main result is a polynomial time bi-criteria approximation algorithm which outputs a (1 -- e)k-partition of the vertex set such that each piece has expansion at most [EQUATION] times OPT. We also study balanced versions of this problem.