@article {IOPORT.05192007,
    author       = {Oh, Jinsoo and Moon, Byung-Ro},
    title        = {On the $L_{2}$-discrepancy.},
    year         = {2007},
    journal      = {Discrete Applied Mathematics},
    volume       = {155},
    number       = {15},
    issn         = {0166-218X},
    pages        = {2039-2042},
    publisher    = {Elsevier Science B.V. (North-Holland), Amsterdam},
    doi          = {10.1016/j.dam.2007.04.021},
    abstract     = {In this article, the following problem is considered. Let $\mathcal{S}$ be a family of subsets of a finite set $V$ and let $\chi:V\rightarrow \{-1,1\}$ be a coloring of $V$. For $S_j\in\mathcal{S}$, let $\chi(S_j):=\sum_{v\in S_j}\chi (v)$ and define the $L_2$-discrepancy of $\mathcal{S}$ with respect to $\chi$ as $$\text{disc}_2(\mathcal{S},\chi):=\biggl(\frac{1}{\vert \mathcal{S} \vert}\sum_j \vert\chi (S_j)\vert^2\biggr)^{1/2}.$$ Furthermore, the $L_2$-discrepancy of $\mathcal{S}$ is defined by $$\text{disc}_2 (\mathcal{S}):=\min_\chi \text{disc}_2 (\mathcal{S},\chi),$$ where the minimum is extended over all colorings $\chi$. The authors of this note discuss a relation of the $L_2$-discrepancy problem to the so called MAX-CUT problem and show two main results. Firstly, it is shown that the $L_2$-discrepancy problem is NP-complete. Moreover, the authors show that there exists a coloring $\chi$ such that $$\biggl(\frac{1}{\vert \mathcal{S} \vert}\sum_j \vert\chi (S_j)\vert^2\biggr)^{1/2}\le\sqrt{\vert V\vert}.$$},
    reviewer     = {Peter Kritzer (Salzburg)},
    identifier   = {05192007},
}