کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420025 683886 2007 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the L2L2-discrepancy
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the L2L2-discrepancy
چکیده انگلیسی

For a family of subsets SS of a finite set VV, a coloring χ:V→{-1,1}χ:V→{-1,1}, and Sj∈SSj∈S, let χ(Sj)=∑v∈Sjχ(v)χ(Sj)=∑v∈Sjχ(v). We consider the problem to minimize ∑jχ(Sj)2∑jχ(Sj)2 and we call the problem L2L2-discrepancy problem. We show that the problem is NP-complete, and we also provide an upper bound for the L2L2-discrepancy.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 15, 15 September 2007, Pages 2039–2042
نویسندگان
, ,