Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems
详细信息 查看全文
- 作者：Mohammad Khairul Hasan ; hasan@kaist.ac.kr" class="auth_mail" title="E-mail the corresponding author ; Kyung-Yong Chwa kychwa@jupiter.kaist.ac.kr" class="auth_mail" title="E-mail the corresponding author
- 关键词：Approximation algorithm ; Sparsest cut ; Graph partitioning ; Linear programming ; Clustering
- 刊名：Journal of Computer and System Sciences
- 出版年：2016
- 出版时间：September 2016
- 年：2016
- 卷：82
- 期：6
- 页码：1044-1063
- 全文大小：574 K
文摘
- class="listitem" id="list_ls0010">
- class="label">•
An O(log t) bicriteria approximation algorithm for the Weighted t-USC problem.
- class="label">•
The first approximation algorithm with approximation factor independent of n.
- class="label">•
For class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016000295&_mathId=si11.gif&_user=111111111&_pii=S0022000016000295&_rdoc=1&_issn=00220000&md5=3649903286590d7655214c905c83a69d" title="Click to view the MathML source">t=no(1)class="mathContainer hidden">class="mathCode"> the algorithm gives the best approximation factor.
- class="label">•
The algorithm is deterministic and requires solving a LP instead of a SDP.
- class="label">•
Approx algorithms for Weighted k-Unbalanced Cut and Min–Max k-Partitioning problems.