2001 | OriginalPaper | Buchkapitel
Structured Randomized Rounding and Coloring
Extended Abstract
verfasst von : Benjamin Doerr
Erschienen in: Fundamentals of Computation Theory
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we propose an advanced randomized coloring algorithm for the problem of balanced colorings of hypergraphs (discrepancy problem). It allows to use structural information about the hypergraph in the design of the random experiment. This yields colorings having smaller discrepancy than those independently coloring the vertices. We also obtain more information about the coloring, or, conversely, we may enforce the random coloring to have special properties. Due to the dependencies, these random colorings need fewer random bits to be constructed, and computing their discrepancy can be done faster. We apply our method to hypergraphs of d-dimensional boxes. Among others, we observe a factor 2d/2 decrease in discrepancy and a reduction of the number of random bits needed by a factor of 2d.Since the discrepancy problem is a particular rounding problem, our approach is a randomized rounding strategy for the corresponding ILP-relaxation that beats the usual randomized rounding.