Partitioning activities for agents

Fatma Özcan, V. S. Subrahmanian

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1218-1223
Number of pages6
JournalIJCAI International Joint Conference on Artificial Intelligence
StatePublished - 2001
Externally publishedYes
Event17th International Joint Conference on Artificial Intelligence, IJCAI 2001 - Seattle, WA, United States
Duration: Aug 4 2001Aug 10 2001

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Partitioning activities for agents'. Together they form a unique fingerprint.

Cite this