Title :
Multiprocessor document allocation: a genetic algorithm approach
Author :
Frieder, Ophir ; Siegelmann, Hava T.
Author_Institution :
Fac. of Comput. Sci. & Comput. Eng., Florida Inst. of Technol., Melbourne, FL, USA
Abstract :
We formally define the Multiprocessor Document Allocation Problem (MDAP) and prove it to be computationally intractable (NP complete). Once it is shown that MDAP is NP complete, we describe a document allocation algorithm based on genetic algorithms. This algorithm assumes that the documents are clustered using any one of the many clustering techniques. We later show that our allocation algorithm probabilistically converges to a good solution. For a behavioral evaluation, we present sample experimental results
Keywords :
genetic algorithms; information retrieval; multiprocessing systems; parallel algorithms; resource allocation; Multiprocessor Document Allocation Problem; NP complete; behavioral evaluation; clustering techniques; computationally intractable; document allocation algorithm; document clustering; experimental results; genetic algorithm approach; probabilistic convergence; Clustering algorithms; Concurrent computing; Costs; Databases; Genetic algorithms; Information retrieval; Information systems; Memory architecture; Parallel processing; Phased arrays;
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on