TR-84: Deterministic Learning Automata Solutions to the Object Partitioning Problem

Abstract

Let rt = {A1 , … , Aw} be a set of W objects to be equi-partitioned into R classes {P 1 , … , PR}. The objects are accessed in groups, their joint access probabilities being unknown. The intention is that the objects accessed more frequently together are located in the same class. This problem has been known to be NP-hard [30]. In this paper, we propose three deterministic learning automata solutions to the problem. Although the first two are £-optimal, they seem to be practically feasible only when W is small. The last solution, which uses a new learning automaton, demonstrates an excellent partitioning capability. Experimentally, this solution converges an order of magnitude faster than the best known algorithm in the literature [30].