Improved algorithms for weighted and unweighted set splitting problems Conference Paper

abstract

• In this paper, we study parameterized algorithms for the SET SPLITTING problem, for both weighted and unweighted versions. First, we develop a new and effective technique based on a probabilistic method that allows us to develop a simpler and more efficient (deterministic) kernelization algorithm for the unweighted SET SPLITTING problem. We then propose a randomized algorithm for the weighted SET SPLITTING problem that is based on a new subset partition technique and has its running time bounded by O*(2k), which even significantly improves the previously known upper bound for the unweigthed SET SPLITTING problem. We also show that our algorithm can be de-randomized, thus derive the first fixed parameter tractable algorithm for the weighted SET SPLITTING problem. Springer-Verlag Berlin Heidelberg 2007.

name of conference

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

authors

• Chen, Jianer

published proceedings

• COMPUTING AND COMBINATORICS, PROCEEDINGS

author list (cited authors)

• Chen, J., & Lu, S.

complete list of authors

• Chen, Jianer||Lu, Songjian

publication date

• December 2007

published in

• Lecture Notes in Artificial Intelligence  Journal

International Standard Book Number (ISBN) 13

• 978-3-540-73544-1

start page

• 537

end page

• +

volume

• 4598