TR-167: A Hierarchical Stochastic Automaton Solution to the Object Partitioning Problem

Abstract

In this paper we study the object partitioning problem in which the elements of a set Q are accessed by users according to an unknown partitioning E>. The joint access probabilities of the objects are unknown and furthermore, the objects are accessed in groups of unknown size which may or may not be equal. The object partitioning problem involves partitioning the objects into a partition TI isomorphic to E> in such a way that the objects accessed more frequently together are located in the same class. It is well known that this problem is NP-hard [22,23]. In this paper, we propose a fast hierarchical stochastic learning automaton solution to the problem. Unlike the previously reported automaton solutions [24] the number of computations per iteration required by this method is logarithmic in the number of objects to be partitioned. Experimentally, this solution converges much faster than the best known algorithm in the literature which does not use learning automata [22,23].