On-Line Algorithms for 2-Coloring Hypergraphs via Chip Games
Abstract
The problem of 2-coloring hypergraphs is known to be NP-complete. However, for k-hypergraphs H of degree k, and k 10 . the Lovasz local Lemma guarantees the existence of a 2-coloring of H such that no edge is monochromatic. We present an on-line algorithm to find such a coloring for k- hypergraph with fewer than 2k-1 edges. The algorithm also works for k- hypergraphs with no degree constraints and is easily generalized to an algorithm for d-coloring a k-hypergraph with fewer than dk-1 edges. The algorithms are 0(1)-competitve against adaptive on-line adversaries. Further, we show that for k-hypergraphs with 4k edges, there exists a simple on-line adversary which thwarts any on-line 2-coloring algorithm. This adversary generalizes to work against on-line algorithms attempting to d-color k-hypergraphs with 2dk edges. A cleverer on-line adversary is also shown which succeeds against on-line algorithms attempting to 2-color k-hypergraphs with k(1+0)k edges (where 0 is the Golden Ratio). Another on-line adversary is shown which succeeds against on- line 2-coloring algorithms for degree k k-hypergraphs with (3+2 2)k edges. All of these results are achieved using a Chip Game model. We show that on-line algorithms for a scheduling problem follow from these 2-coloring algorithms.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1990
- Accession Number
- ADA230200
Entities
People
- Aditi Dhagat
- Javed A. Aslam
Organizations
- Massachusetts Institute of Technology