Unbalanced Graph Partitioning

来源 :2014全国理论计算机科学学术年会 | 被引量 : 0次 | 上传用户:oyfeng168
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  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.
其他文献
由国家计委、科技部共同编制的《当前优先发展的高技术产业化重点领域指南》近日正式向社会公布。这是我国第一部引导高技术产业化发展的指导性文件。在这份指南中有138个领域被
  Over past decades,there has been more and more large scale sensors deployed in a wide range of application areas.Due to the innate imprecision of sensor obs
会议
以外源亚精胺处理NaCl胁迫下毕氏海蓬子幼苗,研究了外源亚精胺对NaCl胁迫下毕氏海蓬子生长、抗氧化酶活性及光合特性的影响.结果表明,300mmol·L-1NaCl浓度最适宜毕氏海蓬子
  以休眠期的马蹄莲小块茎为试材,进行马蹄莲的脱菌试验.接种前采用种类不同杀菌剂(代森新、代森锰锌、多菌灵)、热处理温度(40、45、50℃)、热处理时间(30、45、60min)和不
一台录音机的磁头磁化了,其简易的测试方法是:给录音机装入新磁带或刚抹音的磁带,将电流电压表连接在录音机输出端上,使输入控制置于“关”位置或使输入电路短路,放一分钟磁
近两年来,牡丹54C3A彩电出现随意关机的故障率较高,主要表现在等待电源指示灯亮,不能开机,且伴有较小的“噗噗”声;或能开机,但数分钟后又自动关机,这种故障出现后,有的彩电
ECI电讯公司宣布,由其研制的Hi-TV系统现在已具备支持基于ATM的IP应用功能。Hi-TV系统的这项新功能。(支持基于ATM的IP应用)专为满足广播和电视后期制作的紧迫需要而设计,该
  A k-total coloring of a graph G is a map σ: V (G)∪E(G)→{1,2,...,k} such that no two adjacent or incident elements of V(G)∪E(G) receive the same color.Th
会议
电脑一族防止颈肩腕综合征你是否有颈肩腕综合征?如果你是经常使用电脑的,曾出现过以下症状并持续了一段时间,有可能患了与职业有关的颈肩综合征:1.在电脑前工作一段时间后,
  Cloud computing is a new emerging way by which hardware and software resources can be shared on-demand to computers and other devices via the Internet.Cloud
会议