Non-independent randomized rounding and coloring

DOI10.1016/J.DAM.2005.05.015MaRDI QIDQ2489958zbMATH OpenOpenAlexFDO

Authors 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

DiscrepancyHypergraph coloringRandomized algorithmsRandomized roundingInteger linear programming

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Recommendations

• scientific article; zbMATH DE number 1839472
• Approximating Independent Set and Coloring in Random Uniform Hypergraphs
• A randomized algorithm for \(k\)-colorability
• scientific article; zbMATH DE number 2079377
• Randomized algorithms for colourings of hypergraphs
• Colouring Non-sparse Random Intersection Graphs
• Improved bounds for randomly sampling colorings via linear programming
• Randomly colorable graphs in greedy coloring
• Coloring Random and Semi-Random k-Colorable Graphs
• The Randomized Coloring Procedure with Symmetry-Breaking

Cites work

• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 2119753 (Why is no real title available?)
• scientific article; zbMATH DE number 863495 (Why is no real title available?)
• scientific article; zbMATH DE number 3257050 (Why is no real title available?)
• Coloring the projective plane
• Communication Complexity
• Discrepancy of set-systems and matrices
• Geometric discrepancy. An illustrated guide
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Integral approximation sequences
• Multicolour Discrepancies
• On the discrepancy of combinatorial rectangles
• Optimal roundings of sequences and matrices
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Remark concerning integer sequences
• Roth's estimate of the discrepancy of integer sequences is nearly sharp
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The tail of the hypergeometric distribution
• Tight upper bounds for the discrepancy of half-spaces
• Vergleich der hypergeometrischen mit der Binomial-Verteilung
• ``Integer-making theorems

Cited in

(4)

• scientific article; zbMATH DE number 1839472 (Why is no real title available?)
• Dependent Randomized Rounding: The Bipartite Case
• scientific article; zbMATH DE number 1688362 (Why is no real title available?)
• Practical algorithms for low-discrepancy 2-colorings

This page was built for publication: Non-independent randomized rounding and coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489958)