کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429755 | 687667 | 2016 | 20 صفحه PDF | دانلود رایگان |

• 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)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.
We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph G=(V,E)G=(V,E) with edge-weights w:E→R≥0w:E→R≥0 and vertex-weights η:V→R+η:V→R+ are given. The goal is to find a vertex set S⊆VS⊆V with |S|≤t|S|≤t while minimizing w(S,V\S)/η(S)w(S,V\S)/η(S), where w(S,V\S)w(S,V\S) is the total weight of the edges with exactly one endpoint in S and η(S)=∑v∈Sη(v)η(S)=∑v∈Sη(v). For this problem, we present a (O(logt),1+ϵ)(O(logt),1+ϵ) factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when t=no(1)t=no(1). We also present better approximation algorithms for Weighted ρ-Unbalanced Cut and Min–Max k-Partitioning problems.
Journal: Journal of Computer and System Sciences - Volume 82, Issue 6, September 2016, Pages 1044–1063