Randomized Algorithm For 3-Set Splitting Problem and it's Markovian Model
نویسندگان
1 University of Tehran, College of Engineering, Faculty of Enginering Science
2 Department of Algorithms and Computation, University of Tehran
3 Department of Algorithms and Computation, University of Tehran
4 University of Tehran, College of Engineering, Faculty of Enginering Science
doi
10.22059/jac.2016.7944چکیده
In this paper we restrict every set splitting problem to the special case in which every set has just three elements. This restricted version is also NP-complete. Then, we introduce a general conversion from any set splitting problem to 3-set splitting. Then we introduce a randomize algorithm, and we use Markov chain model for run time complexity analysis of this algorithm. In the last section of this paper we introduce "Fast Split" algorithm.
