hide
Free keywords:
-
Abstract:
We propose an advanced randomized coloring algorithm for the problem of
balanced colorings of hypergraphs (discrepancy problem). Instead of
independently coloring the vertices with a random color, we try to use
structural information about the hypergraph in the design of the random
experiment by imposing suitable dependencies. This yields colorings having
smaller discrepancy. We also obtain more information about the coloring, or,
conversely, we may enforce the random coloring to have special properties.
There are some algorithmic advantages as well.
We apply our approach to hypergraphs of d-dimensional boxes and to finite
geometries. Among others results, we gain a factor 2d/2 decrease in the
discrepancy of the boxes, and reduce the number of random bits needed to
generate good colorings for the geometries down to (from n). The latter also
speeds up the corresponding derandomization by a factor of .
