Online Retweet Recommendation with Item Count Limits

Some Twitter accounts provide information to the followers not by publishing their own tweets but by retweeting (i.e., Forwarding) useful information from their friends. These accounts need to select an appropriate number of tweets that match the followers´ interests. If they retweet too many or too few tweets, it annoys the followers or degrade the value of the accounts. They also need to retweet them in a timely manner. If they retweet a tweet long after they receive it, the informational value of the tweet may diminish before the followers read it. There is, however, a trade-off between these two requirements. If they select tweets after seeing all the candidates, they can select the best given number of tweets, but in order to provide timely information, they have to decide to (or not to) retweet each tweet before seeing all the following candidates. In order to help the management of such Twitter accounts, we developed a system that reads a sequence of tweets from the friends one by one, and select a given number of (or less) tweets in an online (or near-online) fashion. In this paper, we propose four algorithms for it. Two of them give priority to the timeliness, and make a decision immediately after reading a new tweet by comparing its score with a threshold. The other two give priority to the selection quality, and make a decision after seeing some following tweets: after seeing incoming tweets for a fixed length of time or after seeing a fixed number of tweets. The former two are truly online algorithms and the latter two are near-online algorithms. Our experiment shows that the near-online algorithms achieve high selection quality only with acceptable time delays.