de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Non-independent randomized rounding and coloring

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Doerr, B. (2006). Non-independent randomized rounding and coloring. Discrete Applied Mathematics, 154, 650-659.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2388-4
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 .