Non-independent randomized rounding and coloring

AbstractWe 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 O(n) (from n). The latter also speeds up the corresponding derandomization by a factor of n