Experimental Study of Non-oblivious Greedy and Randomized Rounding Algorithms for Hypergraph b-Matching.

We consider the b-matching problem in a hypergraph on n vertices and edge cardinality bounded by ℓ. Oblivious greedy algorithms achieve approximations of ]> and (ℓ + 1)^− 1 independently of b (Krysta 2005). Randomized rounding achieves constant-factor approximations of 1 − ε for large b, namely b = Ώ(ε^− 2, ln n), (Srivastav and Stangier 1997). Hardness of approximation results exist for b = 1 (Gonen and Lehmann 2000; Hazan, Safra, and Schwartz 2006). In the range of 1 < b « ln n, no close-to-one, or even constant-factor, polynomial-time approximations are known. The aim of this paper is to overcome this algorithmic stagnation by proposing new algorithms along with the first experimental study of the b-matching problem in hypergraphs, and to provide a first theoretical analysis of these algorithms to some extent. We propose a non-oblivious greedy algorithm and a hybrid algorithm combining randomized rounding and non-oblivious greedy. Experiments on random and real-world instances suggest that the hybrid can, in terms of approximation, outperform the known techniques. The non-oblivious greedy also shows a better approximation in many cases than the oblivious one and is accessible to theoretic analysis. [ABSTRACT FROM AUTHOR]