Partitioning activities for agents

There are now numerous agent applications that track interests of thousands of users in situations where changes occur continuously. [Shim et al., 1994] suggested that such agents can be made efficient by merging commonalities in their activities. However, past algorithms cannot merge more than 10 or 20 concurrent activities. We develop techniques so that a large number of concurrent activities (typically over 1000) can be partitioned into components (groups of activities) of small size (e.g. 10 to 50) so that each component's activities can be merged using previously developed algorithms (e.g. [Shim et al., 1994]). We first formalize the problem and show that finding optimal partitions is NP-hard. We then develop three algorithms - Greedy, A*-based and BAB (branch and bound). A*-based and BAB are both guaranteed to compute optimal solutions. Greedy on the other hand uses heuristics and typically finds suboptimal solutions. We implemented all three algorithms. We experimentally show that the greedy algorithm finds partitions whose costs are at most 14% worse than that found by A*-based and BAB - however, Greedy is able to handle over thousand concurrent requests very fast while the other two methods are much slower and able to handle only 10-20 requests. Hence, Greedy appears to be the best.