Non-independent randomized rounding and coloring

DOI10.1016/J.DAM.2005.05.015zbMATH Open1120.90032OpenAlexW2037463483MaRDI QIDQ2489958FDOQ2489958

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

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

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)

Cites Work

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

Cited In (4)

• Dependent Randomized Rounding: The Bipartite Case
• Title not available (Why is that?)
• Practical algorithms for low-discrepancy 2-colorings
• Title not available (Why is that?)

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)