A randomized approximation algorithm for parameterized 3-D matching counting problem Conference Paper uri icon

abstract

  • The computational complexity of counting the number of matchings of size k in a given triple set remains open, and it is conjectured that the problem is infeasible, In this paper, we present a fixed parameter tractable randomized approximation scheme (FPTRAS) for the problem. More precisely, we develop a randomized algorithm that, on given positive real numbers and , and a given set S of n triples and an integer k, produces a number h in time 0(5.483kn2ln(2/)/2) such that prob[(1 - e)h0 h (1 + )h0] 1 - where h0 is the total number of matchings of size k in the triple set S. Our algorithm is based on the recent improved color-coding techniques and the Monte-Carlo self-adjusting coverage algorithm developed by Karp and Luby. Springer-Verlag Berlin Heidelberg 2007.

name of conference

  • Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings

published proceedings

  • COMPUTING AND COMBINATORICS, PROCEEDINGS

author list (cited authors)

  • Liu, Y., Chen, J., & Wang, J.

complete list of authors

  • Liu, Yunlong||Chen, Jianer||Wang, Jianxin

publication date

  • December 2007