Improved Parameterized Set Splitting Algorithms: A Probabilistic Approach Academic Article

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 *(2 k ), which is significantly better than that of the previous best deterministic algorithm (which only works for the simpler unweighted set splitting problem) of running time O *(2.65 k ). We also show that our algorithm can be de-randomized, which leads to a deterministic parameterized algorithm of running time O *(4 k ) for the weighted set splitting problem and gives the first proof that the problem is fixed-parameter tractable. 2008 Springer Science+Business Media, LLC.

authors

• Chen, Jianer

published proceedings

• Algorithmica

author list (cited authors)

• Chen, J., & Lu, S.

citation count

• 15

complete list of authors

• Chen, Jianer||Lu, Songjian

publication date

• August 2009

publisher

• Springer Nature  Publisher

published in

• Algorithmica: an international journal in computer science  Journal

keywords

• 46 Information And Computing Sciences
• 49 Mathematical Sciences
• 4901 Applied Mathematics

Digital Object Identifier (DOI)

• 10.1007/s00453-008-9206-y

start page

• 472

end page

• 489

volume

• 54

issue

• 4

URL

• http://dx.doi.org/10.1007/s00453-008-9206-y