Experimental Study of Non-oblivious Greedy and Randomized Rounding Algorithms for Hypergraph b-Matching (Extended Abstract)

摘要

We consider the b-matching problem in a hypergraph on n vertices and edge cardinality bounded by e. Oblivious greedy algorithms achieve approximations of (n~(1/2)+1)~(-1) and (l+1)~(-1) independently of b (Krysta 2005). Randomized rounding achieves constant-factor approximations of 1 - ∈ for large 6, 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 6-matching problem in hyper-graphs, 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.