A (1 + ?)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lov�sz Local Lemma

DOI10.1002/rsa.20016zbMath1075.68102OpenAlexW2091047457WikidataQ124987154 ScholiaQ124987154MaRDI QIDQ4810508

Mohammad R. Salavatipour

Publication date: 16 August 2004

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20016

zbMATH Keywords

probabilistic methodhypergraph coloringLovász Local Lemmarandom trial

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

NP-hard and linear variants of hypergraph partitioning

Cites Work

• A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)
• Unnamed Item
• Unnamed Item
• Unnamed Item