Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems
作者：
Highlights：
• An O(log t) bicriteria approximation algorithm for the Weighted t-USC problem.
• The first approximation algorithm with approximation factor independent of n.
• For t=no(1) the algorithm gives the best approximation factor.
• The algorithm is deterministic and requires solving a LP instead of a SDP.
• Approx algorithms for Weighted k-Unbalanced Cut and Min–Max k-Partitioning problems.
摘要
•An O(log t) bicriteria approximation algorithm for the Weighted t-USC problem.•The first approximation algorithm with approximation factor independent of n.•For t=no(1) the algorithm gives the best approximation factor.•The algorithm is deterministic and requires solving a LP instead of a SDP.•Approx algorithms for Weighted k-Unbalanced Cut and Min–Max k-Partitioning problems.
论文关键词：Approximation algorithm,Sparsest cut,Graph partitioning,Linear programming,Clustering
论文评审过程：Received 23 December 2012, Accepted 15 March 2016, Available online 30 March 2016, Version of Record 10 June 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2016.03.004
