@conference {17825,
title = {Partitioning activities for agents},
booktitle = {INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE},
volume = {17},
year = {2001},
month = {2001///},
pages = {1218 - 1228},
abstract = {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{\textquoteright}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 {\textemdash} 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.
},
author = {Ozcan,F. and V.S. Subrahmanian}
}