| 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’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.
|
