کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429755 687667 2016 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph 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)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(log⁡t),1+ϵ)(O(log⁡t),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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 82, Issue 6, September 2016, Pages 1044–1063
نویسندگان
, ,