Algorithm for Linear Number Partitioning into Maximum Number of Subsets
Hussain Md.MehedulIslam, Mohammad Obaidur Rahman · International Journal of Computer Applications · 2012
The number partitioning problem is to decide whether a given multiset of integers can be partitioned into two "halves" of given cardinalities such that the discrepancy, the absolute value of the difference of their sums is minimized.While Partitioning problem is known to be NP-complete, only few studies have investigated on its variations.Number partitioning problem has a wide range of practical application, like: multiprocessor scheduling, minimization of VLSI circuit size and delay, also used in public key cryptography, message verification, computer password, voting manipulation and bin packing.While lots of investigation have been made for two-way partitioning, only a few for multi-way partitioning, while most of them are not feasible for real time environment.We introduce an improved multi-way partitioning algorithm which is feasible for real time environment.It returns maximum number of subset that can be made based on the order of the numbers as they appear.Maximum number of subset helps us to preempt any process & serve higher priority process with extremely low overhead cost in multiprocessor process scheduling.