%0 Conference Paper
%B INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE
%D 2001
%T Partitioning activities for agents
%A Ozcan,F.
%A V.S. Subrahmanian
%X There are now numerous agent applications thattrack interests of thousands of users in situations where changes occur continuously. [Shim et al., 1994] suggested that such agents can be made effi- cient by merging commonalities in their activities. However, past algorithms cannot merge more than 10 or 20 concurrent activities. We develop tech- niques so that a large number of concurrent activ- ities (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 prob- lem 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 heuris- tics and typically finds suboptimal solutions. We implemented all three algorithms. We experimen- tally 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.
%B INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE
%V 17
%P 1218 - 1228
%8 2001///
%G eng