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

DOI10.1002/RSA.20016MaRDI QIDQ4810508zbMATH OpenOpenAlexWikidataFDO

Authors Mohammad Salavatipour

Publication date 16 August 2004

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

hypergraph coloringLovász Local Lemmaprobabilistic methodrandom trial

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2079358
• scientific article; zbMATH DE number 1445282
• New algorithmic aspects of the local lemma with applications to routing and partitioning
• Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
• A parallel algorithmic version of the local lemma

Cites work

• A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)
• scientific article; zbMATH DE number 1301961 (Why is no real title available?)
• scientific article; zbMATH DE number 1775440 (Why is no real title available?)
• scientific article; zbMATH DE number 2119715 (Why is no real title available?)

Cited in

(6)

• NP-hard and linear variants of hypergraph partitioning
• New algorithmic aspects of the local lemma with applications to routing and partitioning
• scientific article; zbMATH DE number 1305457 (Why is no real title available?)
• scientific article; zbMATH DE number 2079358 (Why is no real title available?)
• Improved bounds and algorithms for hypergraph 2-coloring
• Variable version Lovász local lemma: a tale of two boundaries

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

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