Non-independent randomized rounding and coloring
From MaRDI portal
Publication:2489958
DOI10.1016/j.dam.2005.05.015zbMath1120.90032MaRDI QIDQ2489958
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
Randomized rounding; Randomized algorithms; Discrepancy; Hypergraph coloring; Integer linear programming
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