Unbalanced Graph Partitioning

来源 :2014全国理论计算机科学学术年会 | 被引量 : 0次 | 上传用户:panjintao
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  We investigate the unbalanced cut problems.A cut (A;B) is called unbalanced if the size of its smaller side is at most k (called k-size) or exactly k (called Ek-size),where k is an input parameter.An s-t cut (A;B) is called unbalanced if its s-side is of k-size or Ek-size.We consider three types of unbalanced cut problems,in which the quality of a cut is measured with respect to the capacity,the sparsity,and the conductance,respectively.We show that even if the input graph is restricted to be a tree,the Ek-Sparsest Cut problem (to find an Ek-size cut with the minimum sparsity) is still NP-hard.We give a bicriteria approximation algorithm for the k-Sparsest Cut problem (to find a k-size cut with the minimum sparsity),which outputs a cut whose sparsity is at most O(log n) times the optimum and whose smaller side has size at most O(log n)k.As a consequence,this leads to a (O(log n);O(log n))-approximation algorithm for the Min k-Conductance problem (to find a k-size cut with the minimum conductance).We also prove that the Min k-Size s-t Cut problem is NP-hard and give an O(log n) approximation algorithm for it.The approximation ratios given in this paper for k-Sparsest Cut,Min k-Conductance,and Min k-Size s-t Cut are the best ratios currently known for the corresponding problems.
其他文献
Routing algorithm with more flexibility and fewer virtual channels is essential for high performance multicomputer systems.For three-dimensional mesh-connected networks,the traditional planar-adaptive
It is well-known that model combination can improve prediction performance of regression model.We investigate the model combination of Support Vector Regression (SVR) with regularization path in this
This paper designed a kind of optimization algorithm for image registration.By combining with cultural particle swarm optimization (CPSO),a novel image registration algorithm is outlined in this paper
Profinite topology plays a key role in formal languages.Depending on the fact that Boolean algebra of regular languages is in one-to-one correspondence to clopen of profinite topological space,we prov
To further explore the up-to techniques for bisimulation in the coalgebra setting,we investigate a special kind of functor,i.e.,product functor in this paper.Specifically,when F is the product of n su
Motivated by a previous work showing a new NP-complete decision problem,the Multistage graph Simple Path problem (MSP) possesses a novel polynomial-time heuristic algorithm,which has undergone extensi
Spatio-Temporal properties are the intrinsic properties of Cyber-Physical System(CPS),the correlation in space and time between computing and physical entities should be fully considered in CPS modeli
With the rapid development of cloud computing,how to effectively improve the utilization of computing resources in a cloud becomes a difficult problem.Therefore,a large number of distributed and paral
Considering poor quality and high noise in medical data,we propose an ensemble classifier based on support vector machine (SVM) and apply this classifier to health identification.Health identification
An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G such that adjacent vertices get numbers at least two apart,and vertices at distance two get distinct numbe