Article ID Journal Published Year Pages File Type
420025 Discrete Applied Mathematics 2007 4 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,