Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420025 | Discrete Applied Mathematics | 2007 | 4 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jinsoo Oh, Byung-Ro Moon,