Non-independent randomized rounding and coloring

DOI10.1016/j.dam.2005.05.015zbMath1120.90032MaRDI QIDQ2489958

Benjamin Doerr

Publication date: 28 April 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.015

zbMATH Keywords

Randomized rounding; Randomized algorithms; Discrepancy; Hypergraph coloring; Integer linear programming

Mathematics Subject Classification ID

90C10: Integer programming

90C05: Linear programming

05C65: Hypergraphs

05C15: Coloring of graphs and hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Coloring the projective plane
• Discrepancy of set-systems and matrices
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• ``Integer-making theorems
• Roth's estimate of the discrepancy of integer sequences is nearly sharp
• The tail of the hypergeometric distribution
• Tight upper bounds for the discrepancy of half-spaces
• Vergleich der hypergeometrischen mit der Binomial-Verteilung
• Integral approximation sequences
• Multicolour Discrepancies
• On the discrepancy of combinatorial rectangles
• Communication Complexity
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Remark concerning integer sequences
• Geometric discrepancy. An illustrated guide