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

$(\sqrt{n}+1)^{-1}$

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.