DEIM Forum 2014 B2-6

ツイート数上限付きのオンラインリツイート推薦手法
趙驍騏†田島敬史††† 京都大学大学院情報学研究科 〒 606–8501 京都市左京区吉田本町 36-1†† 京都大学大学院情報学研究科 〒 606–8501 京都市左京区吉田本町 36-1
E-mail: †x.zhao@dl.kuis.kyoto-u.ac.jp, ††tajima@i.kyoto-u.ac.jp
あらましTwitter のアカウントの中には，自らのツイートの発信を目的とするのではなく，自分のフレンドの投稿をリツイートすることでフォロワーへ情報提供することを目的としているものがある．そのようなアカウントの運用
では，既存のフォロアーを維持することが大切である．よって，フレンドの投稿の中から，よりフォロワーの興味に合う投稿を，より速く，そして，フォロワーにとって過剰とならない適切な発信頻度の範囲内で，選択して発信することが重要となる．そこで，本研究では，オンライン・アルゴリズムによる，ツイート数上限付きリツイート推薦手法を提案する．
キーワード

1. 序Twitter，ナップサック問題，情報フィルタリング

論

情報を発信するのは現実には容易ではない．なぜならば，これらのポータルサイトは多くのユーザ（フレンド）をフォローしこの数年，ソーシャルネットワークサービスの発展に伴い，ており，多くのユーザ（フォロワー）にフォローされているかソーシャルネットワークサービスに関連する多くのウェブあるらである．そのような多くのフレンドからの投稿の選別を，遅いはモバイルベースのアプリケーションが登場した．これらの延を生じさせずに人手で行うのは，速度の面からも，管理者がアプリケーションのおかげでより多くの人がさまざまなディバ

24 時間ツイートを継続的に監視しなければならなくなるといイスにより，情報発信と情報交換が可能になっている．具体的う面からも困難である．さらに，非常に多くのフォロワーの興には，ユーザがソーシャルネットワークが提供しているサービ味の分析も人手では困難である．

スにより，新鮮なイベントの情報やニュースなどのメッセージを投稿し共有することが可能になっている．

そこで，本研究では，オンライン・アルゴリズムによる，ツイート数上限付きリツイート推薦手法を 4 つ提案する．提案手

それらのソーシャルネットワークサービスの中でも，情報源法では，フレンドから投稿が来るたびに，システムがその投稿からの情報収集の手段として有用なメディアとしては，Twitterをフォロワーの興味との合致度などの観点から評価する．そしが注目を集めている．Twitter は 2006 年より運用を開始し，現て，その評価値と決められた期間内のツイート数上限までの残在，2 億人の月間アクティブユーザを有している．そのユーザの数とを合わせて考慮し，配信すべきかどうかを短時間内に決定

中には，自分が独自の情報を発信するのが目的ではなく，主にする．配信すべきなら，すぐにそのツイートをフォロワーへと自分がフォローしているユーザからの情報をリツイートするこリツイートする．このような手法が実現できれば，高い評価点とでフォロワーへ情報提供することを主な目的としているもの

数を持つ投稿を，許容範囲内の配信数で，配信の遅延を抑えなも多数存在している．これらのユーザはソーシャルネットワーがら自動的に配信できる．実験では 4 つの手法を評価し，結果ク上のポータルサイトのような役割を果たしている．このようより Twitter 上ポータルサイトのためのリツイート推薦はもっなユーザを本論文では単にポータルサイトと呼ぶ．ともふさわしいのは「一定時間ごと推薦」であることが分かっ

このようなポータルサイトの運用では，ユーザの注目を集めた．本研究での提案手法により，管理者の負担を低減するととるため，フォローしているユーザの興味に関連する投稿をリツもに，人手による配信よりも迅速かつ適切な情報の伝達を行うイートすることが重要である．また，Twitter 上の情報の拡散ことが期待できる．

速度は速く，一つのメッセージの価値が持続する時間は 48 時

本稿の次章以降の構成は次のとおりである．まず，2 章では間しかないといわれている．よって，情報の価値が減少する前関連研究を紹介し，本研究の位置付けを説明する．次に，3 章にフォロワーへと配信するためには，フレンドから発信されたではリツイート推薦にあたってのツイートの評価手法を説明すツイートを，できるだけ遅延なくリツイートすることが必要でる．4 章では，オンライン・アルゴリズムで，配信上限数の範ある．

囲内で最適なツイートを選択する手法を説明する．5 章では実そして，情報発信の量についても適切な発信数の範囲内に抑えることを考える必要がある．投稿数が多すぎると，フォロワーにとっては迷惑であり，少なすぎるとポータルサイトの発信能力，価値が問われ，フォロワーが離れていく．
しかし，人手によって，上述した三つの条件を満たした形で験の説明を行い，6 章では実験結果の考察について述べる．最後に 7 章では，結論とまとめを説明する．

2. 関 連 研 究
本章では関連研究について紹介する．

2. 1 リツイート推薦
近年，盛んに研究が行われたツイート推薦に比べると，リツイート推薦に関する研究はまだ数少ない．

ワーの興味に合ったリツイートの推薦を行う．
また，本研究で提案する手法の一番の特徴は，オンラインアルゴリズムにより，全てのツイートを見る前に，制限ツイート

Macskassy ら [1] は，ユーザのリツイートという行為を理解数以内で，できるだけ最適なツイートを選ぶことを実現する点するためのモデルとして，「ジェネラルモデル」「直近コミュニであり，ツイート推薦やリツイート推薦に関して，そのようなケーションモデル」「トピックモデル」「同類性モデル」ということを行う研究はこれまでには行われていない．

四つの情報伝達モデルを提案した．ジェネラルモデルはユーザが自分の意思で読んだツイートをランダムにリツイートするという前提に設計された．そして，ユーザが読んでから長い時間

2. 2 オンラインナップサック問題
今回，取り組むポータルサイトのリツイート推薦においては，手法に対して以下の三点が求められている．

を経ったツイートをリツイートする確率はごく直近に読んだツ•フォロワーの興味に合うものを推薦する．

イートをリツイートする確率より低いと仮定する．ジェネラル•

推薦するかどうかの決定を迅速に行う．

モデルは，このように, 時間リツイートしたときの時刻と本来•一定期間内に推薦する数を指定された上限以内に抑える．の投稿の時刻の間の時間間隔とリツイートされる確率間の関このような問題は，フォロワーの興味に合う度合いをそのツ係に着目する．一方，直近コミュニケーションモデルは，リツイートの価値とし，発信数の上限をナップサックの容量と考えイートという行為と直前のコミュニケーションの間の関係を示れば，オンラインナップサック問題として定式化できる．

す．トピックモデルと同類性モデルにおいては，ほかの投稿とオンラインナップサック問題のアルゴリズムの効率は競合比

リツイートした投稿との間のトピック面での類似度とユーザプで評価される．競合比とは，最適なオフラインアルゴリズムにロフィールにおける類似度でリツイート行為をモデリングする対して，そのオンラインアルゴリズムは何倍ぐらいコストがかことを図る．これらのモデルは，大量のデータに基づいてモデかるか，ということである．競合比が小さければ，小さいほどリングと評価を行っているものであるため，本研究で行うようアルゴリズムの効率がよい．

な，あるポータルサイトという個別のユーザのリツイート行為

オ ン ラ イ ン ナップ サック 問 題 の 一 般 形 は Marchetti-のモデリングに適用するには，ノイズに弱いという問題がある．

Spaccamela ら [4] によって研究され，一般形のオンラインナッ

Uysal ら [2] はリツイート推薦用の識別器を提案した．提案

プサック問題においては，競合比に上限が保証できるアルゴリ

された識別器はツイート著者の属性，ツイートの属性，ツイーズムが存在しないことが証明されている．

トの内容，そしてターゲットユーザの属性からなる四つの特徴

一方，一般形の他に，オンラインナップサック問題のいくつで学習を行う．識別器の目的はあるツイートが届いたときに，かの特殊なケースについても，さまざまな研究がなされている．

上述した四つの特徴量からみて，ターゲットユーザがリツイー

Iwama ら [5] は除去可能オンラインナップサック問題についてトする確率が高いかどうかを推定する．

よい競合比が得られるアルゴリズムを提案した．除去可能ナッ

Peng ら [3] は CRFs（Conditional Random Fields，条件付プサック問題と一般形との違いは，除去可能ナップサック問題

き確率場）でユーザのリツイートという意思決定のプロセス

では一度ナップサックに入れたアイテムを再び外すことが可能をモデリングする手法を提案した．提案したモデルは三つのであることである．ただし，一度，外されたアイテムは再利用

ユーザーツイートの特徴，すなわち，ツイート内容による影響，できない．各時点で，現在ナップサックに入っているアイテムユーザネットワークによる影響と，投稿間の遅延の三つをベー集合を最適化することにより，一般のナップサック問題よりもスにモデリングした．CRFs のパラメータは過去にリツイート良い競合比が得られるが，このような最適化はポータルサイトしたツイートから最尤推定で推定される．正解率，効率向上のにとってリツイートしたものを頻繁に削除することになる．先ため，ソーシャルグラフのパーティションと近似ネットワークに読んだ投稿がいつの間にかに消えるのはフォロワーにとって関係を取りいれた手法を提案している．

は不快であり，またツイート数の制限の意味もささなくなるた

上述した三つの関連研究はリツイートという行為をモデリングしようとするものである．ただし，これらのモデリングは，め，除去可能オンラインナップサック問題の手法は本論文への適用は不適切であろう．

あるターゲットユーザが過去に何をリツイートすべきかを明確

確率的オンラインナップサック問題もオンラインナップサッに分かった上で適切なリツイートをしたという仮説に基づいて，ク問題の特殊な形の一例である．Chakrabarty ら [6] は，アイ過去のデータを元に今後，リツイートすべきツイートを推薦す

テムの価値と重みの比について，上限を U ，下限を L とするオるものである．ポータルサイトは多くのフォロワーを有していンラインナップサック問題に取り組んだ．さらに，アイテムのて，フォロワーの興味も把握しきれない上，フォロワーの内容重みがナップサックの容量に比べ，非常に小さいと仮定したうも変動するため，過去の投稿は必ずしも現在のフォロワーの興えで，競合比が log (U/L) + 1 となるアルゴリズムを提案した．

味に合うとは言い切れない．よって，過去の投稿履歴の分析結

しかし，本研究においては，推薦数の上限が有限の件数になる

果でフォロワーの興味と合致するものを選択するのは困難であので，「アイテムの重みがナップサックの容量に比べ，非常に小り，本研究の目的には適用できない．

さい」との仮定が成り立たないため，この手法の適用は困難で本研究におけるリツイート推薦は，リツイートの履歴を分析する代わりに，フォロワーの興味を理解することで，フォロある．

3. 4 ツイートの評価

3. 投稿の評価

本研究では，ポータルサイトのフレンドからのツイートの評

本研究においては，リツイート推薦はフォロワーの興味に基づいて行う．Twitter は，他のソーシャルネットワークサービ

価はフォロワーの興味との一致度で評価する．手順は以下のように行われる．

ス，たとえば Facebook などと違い，ユーザが自分の興味を明（ 1 ） フォロワーのフィルタリングにより，フォロワーのう確に記述する場所は用意されていない．そこで，本研究では，

ち，アクティブユーザ (以下ではアクティブフォロワーとする)フォロワーの興味を，そのフォロワーが投稿したツイートの内を抽出する．

容と，そのユーザのプロフィールから推定する．

（ 2 ） アクティブフォロワーのツイート，プロフィールを分

3. 1 ツイート内容による興味推定析し，各語の TF-IDF 値からなる興味ベクトルを抽出する．すツイートの内容分析においては，LDA（Latent Dirichlet Al-べてのアクティブフォロワーの興味ベクトルの重心を求め，フォlocation，潜在的ディリクレ配分法）をベースにしたトピックロワー興味ベクトルとする．

モデルによる分析ではなく，文書ベクトルモデルをベースにし（ 3 ） 投稿から語を抽出し，フォロワーの興味と同じ文書ベた TF-IDF 法を使用する．これは，ツイートの平均の長さがクトル空間に射影し，射影した結果を投稿ベクトルと呼ぶ．

30 文字と短く，多くのツイートはトピック分析には不向きなた（ 4 ） 投稿ベクトルとフォロワー興味ベクトルのコサイン相めである．TF-IDF 法で用いる tfidf 値は以下の式より求めら関値をツイートの評価値 s とする．

れる．

4. オンライン処理でのリツイート推薦

tfidf = tf ∗ idf
ni,jtfi,j = ∑nk i,k|D|
idfj = log|{di |ni,j > 0}|

(1)
(2)
(3)

本研究では，決められた発信数の枠 c 内で，なるべくフォロワーの興味と一致度が高いツイートを，オンライン処理で選択する必要がある．簡単化のため，本研究では，日単位で M 個のツイートを上限としてリツイート推薦を行うと仮定する．

ただし，ここで ni,j は語 wj のツイート di での出現頻度，|D|

このような推薦において，Twitter のポータルサイトの現状はあるユーザのすべてのツイートの数である．本研究においてを考慮すると，2.2 節で説明した三つの条件以外に，すでに推は TF-IDF 法でフォロワーの興味を推定する．

薦した項目についてさらに以下のような 1 つの制限を加える：

3. 2 プロフィールによる興味推定
Twitter では，ユーザは自分のプロフィールを書くことがですでに推薦した項目を取り消し，推薦枠を再利用することができない．

きる．一部のユーザはプロフィールにこれまでの経歴や自分のその理由として，Twitter 上の情報拡散が速く，推薦した項趣味を書いている．そこで，本研究では，プロフィールに出現目が取り消される前に，多くにフォロワーがすでに読んでいる．

している語もフォロワーの興味の推定に利用する．

それらのフォロワーにとって，推薦枠の再利用は上限数を引き事前にプロフィールが書いたユーザのうちのランダムサンプリングにより 200 人のユーザに対して，プロフィールを調査し上げることに違いはない．よって，本研究において，推薦済みのツイートの取り消しはできないことにしている．

た結果，興味推定に有用な情報が含まれるプロフィールは半数上述したを満たす推薦は，今後の良いツイートの数が不明以下にとどまった．そして，使用された語，文章の書き方は非な状態で意思決定する必要がある．本研究における「良い」ツ

常に多様でスパースであった．

イートの数が予想より多くなり，少なくなる可能性がある．た

事前調査のことを受け，プロフィールに対しては，LDA やTF-IDF による分析には向かないと考えられる．本研究において，プロフィールから収集された語（品詞が名詞であるもの）だし，今後のツイートを見てから推薦するのでは遅延が発生する．遅延と推薦の精度の間にトレードオフが生じる．
本研究では，推薦の精度と遅延に着目し，4 つの手法を提案をユーザの興味を示すヒントと捉える．プロフィールによる興する．

味推定は，既存のツイートから分析した興味の精度を向上させ•

過去の最適値による閾値決定

るために，使用する．ツイートによる推定されたベクトルのう•

確率分布による閾値決定

ちに，TF-IDF 値が低い語と入れ替える．

•一定時間ごと推薦

3. 3 フォロワーのフィルタリング•

一定件数ごと推薦

ポータルサイトのフォロワーの中には多数の非アクティブ

4 つの手法は遅延時間重視の「リアルタイム型」，そして質をユーザが存在していることがある．そこで，フォロワーの興味重視し遅延を認める「非リアルタイム型」に分類することがで推定にあたっては，ノイズを低減するために，これらの非アクきる．
「過去の最適値による閾値決定」と「確率分布による閾値ティブユーザを除いたユーザのみを考慮すべきである．本研究決定」は「リアルタイム型」に該当するが，「一定時間ごと推薦」

では，以下の基準をすべて満たしているユーザを非アクティブと「一定件数ごと推薦」は「非リアルタイム型」に該当する．

ユーザとする．

•

毎週投稿するツイートの件数が 1 件以下である．

•2 か月の間に，フォローの数を変更していない．

「リアルタイム型」の手法ら，Kellerer ら [7] によるオンラインナップサック問題の閾値アルゴリズムを拡張し，推薦を行う．
以下では四つの手法それぞれについて説明を行う．

4. 1 過去の最適値による閾値決定

5. 実

本手法では，過去のオフラインでの推薦の結果を活用し，閾験値として使用する．最近の数日のフレンドからのツイートにつ5. 1 実験データ

いてフォロワーの興味との合致度を求め，各日について，その本研究では，Twitter 上の 7 個のポータルサイトを実験対日のツイートの中で評価値が降順で M 番目であるツイートの象とし，それら 7 個のポータルサイトから，Twitter REST

評価値の平均値 s̄ を求め，閾値 θ とする．そして，当日のフレAPI（注 1） を用いて，各サイトのツイートとプロフィールを収集

ンドからのツイートの中で，θ より高い評価点数を持つツイーした．

トを発信数の上限に達するまで推薦していく．

選択されたポータルサイトはすべて以下の条件を満たした．

4. 2 確率分布による閾値決定•アクティブユーザ 300 以上のフォロワーを有する．

本手法では，Kellerer ら [7] によるオンラインナップサック•

サイトが開設された日から 2 年以上が経過している．

•

毎週少なくとも 20 件以上のツイートを投稿する．

KELLERER らによるアルゴリズムでは，ツイートの列 T•

投稿されたツイートのうち，半数以上がリツイートで（アイテム）の総数 |T | が事前に既知であると仮定されている．

ある．

問題の閾値アルゴリズムを，以下のように拡張した．

しかし，フレンドからの投稿数はある程度の変動があり，事前また，各サイトについて，そのサイトのフレンドとフォロにはわからない．本手法では，過去の履歴から最近の数日のフワーについても同様に，ツイートとプロフィールを収集した．

レンドからのツイートの件数の平均値を求め，さらに，当日のただし，Twitter REST API には Rate Limit があり，すべて各時間帯において，その直前の時間帯の投稿件数の変化に基づのフォロワーのデータを収集することは困難である．そこで，7いて適応的に，その時間帯のツイートの件数 |T | を推定する．

サイトのうち，フォロワー数が 2000 を超えるサイトについてさらに，以下の 3 つの仮定で閾値を計算する．

は，1500 人のフォロワーをランダムサンプリングで抽出し，そ•れらのフォロワーについてデータを収集した．

ツイートの評価値はベータ分布に従う

すなわち，評価値 v(t) の確率分布関数をこのようにして，合計 5649 人のユーザの 2013 年 10 月 1 日〜2013 年 12 月 24 日まですべてのツイートを収集した．

f (x; α, β) = B(α, β)−1 xα−1 (1 − x)β−1

表1と書き，累積分布関数を It (α, β) と書く．確率分布の平均値はµ と書く．
•

日本マイクロソフト株式会社 広報

時間内に来るツイートの評価値は予測分布からのランダ

19776 (3091)
4743 (2415)

29

65768 (2497)

153

現区間のツイートの評価値の最大値は max(v(T )) と書

奈良市役所

公式ツイッター

香川県（広聴広報課）
京大生協

上述した，3 つの仮定のもとで，

1718

28

5854 (1749)

30

330

145

1667

57

時計台旅行センター

東京都公園協会広報

Imax(v(T )) (α, β) − Iθ (α, β)c=µ|D(u, T )|が成り立つ．

57

東京都庁広報課

き，過去の履歴より推定できる

1

各サイトは表に書かれた順番 o で，以下では「サイト o」と称する．

2

括弧内の数字はサンプリング後実験で実際に使用したフォロワーの数である．サイト間のフォロワーの重複により，実験中に使用したフォロワー数は 1500 を閾値 θ は

θ = I −1 (Imax(v(T )) (α, β) −フォロワーの数 2 フレンドの数

東大ナビ:東京大学公式イベント情報

ムサンプリングした値の列である•

実験で使用したポータルサイト

サイト名 1

超えた．

µc).
|T |(4)より計算できる．
計算した閾値 µ より評価値の高いツイートを上限まで推薦する．

4. 3 一定時間ごと推薦

5. 2 実験データの前処理
本研究において，収集されたツイートに対して，ストップワードを除去したのち，Mecab（注 2） で形態素解析を行い，品詞が名詞である語のみを抽出して，TF-IDF ベクトルを算出した．

5. 3 パラメータ設定と評価本手法では，1 日の時間をあらかじめ，M 個の区間に分割す

本研究では，一般のユーザが受け入れる同じサイトの投稿数，る．そして，第 n 区間ごとに，その区間内に到達したフレンド「期間ごと推薦」法で一日の時間が割り切れることを考え，毎からのツイートの中で，評価値が n − |O| 位のツイートを推薦日（24 時間）のリツイート推薦数の上限として 6，12，24 のする（O 推薦済みのツイートの件数である）．

三通りを考え，それぞれの場合について前述の四つの推薦手法

4. 4 一定件数ごと推薦
本手法では，まず，当日のフレンドからのツイートの数を過を適用し，手法の有効性を評価した．
各手法の評価にあたっては，すべてのツイートの評価値がわ去の履歴から推定する．具体的には，最近の数日のフレンドからのツイートの件数の平均値 n̄ を推定値として用いる．そしn̄て，フレンドからのツイートが ⌈ M⌉ 件到達するごとに，それらのツイートの中で評価値が 1 位のツイートを推薦する．

（注 1）：The Twitter REST API — Twitter Developers https://dev.

twitter.com/docs/api（注 2）：Mecab https://code.google.com/p/mecab/図 4 競合比の実験結果（各サイト，上限数 24）

図 1 競合比の実験結果

図 2 競合比の実験結果（各サイト，上限数 6）
図5

遅延時間の実験結果

表 2 7 つのポータルサイトの実際の遅延時間
サイト番号 平均値 (秒)図 3 競合比の実験結果（各サイト，上限数 12）

最大値 (秒) 最小値 (秒) 中間値 (秒)18982

11214762215602399661491408

265950313180

74051

258

4775

4330696110518810747510524243247332625663665578893117

60075

716458265742983098とが考えられる．リアルタイム型の両手法のうち，「確率分布による閾値決定」の競合比がもっとも良くなく，確率分布によるかったうえで上位のツイートを推薦するというオフラインでの推薦結果をベースラインとした．
評価にあたっては，以下の 2 つ評価尺度で評価を行った．

•競合比 r閾値決定の仮説がデータの分布から乖離していることが原因として考えられる．
遅延時間に関しては，「非リアルタイム型」の 2 つの手法のう∑t ∈ sonline v(t)∑r=

ち，一定時間ごと推薦の遅延時間は一定件数ごと推薦より少な•にまとめた．本研究で提案した手法の平均遅延時間は実際の平t ∈ sof f line v(t)遅延時間

ツイートを推薦した時の時刻とツイートが届いた時の時刻の差を遅延時間とする．

いことが分かった．
そして，各サイトの実際の推薦による遅延時間を収集し，表 2均値より少ないことが分かり，実用における有効性を確かめた．
よって，本研究において，Twitter 上のポータルサイトのた競合比の平均値そして上限数別の各サイトの競合比はそれぞめのリツイート推薦手法として「一定時間ごと推薦」が最もふ

れ図 1，図 2，図 3，図 4 に示す．上限数の遅延時間の平均値結さわしい．なぜかというと，この手法の意思決定に必要な遅延果はそれぞれ図 5 に示す．

が平均的に少なく，競合比 1 位の一定件数ごと推薦とほぼ同等競合比の結果では，サイト 5 以外，上限数によらず，各手法の競合比の順位が安定している．競合比の平均的な結果からみると，一定件数ごと推薦の競合比が最もよい結果を示している．の競合比を実現していることからである。

6. 結論

一定時間ごと推薦は同等レベルの競合比を実現している．リア

本研究では，Twitter 上のポータルサイトのためのオンライルタイム型推薦の競合比はそれほどよくない．その理由として，ンツイート推薦手法を四つ提案し，実験で評価した．そして，他のアルゴリズムと比較し，意思決定に使える情報が少ないこ

提案手法は他のストリームメディア，たとえば RSS 等にも適用可能である．今後の課題として，適合テクニックを用い，リア
ルタイム推薦の手法の改善すること，および緊急時に多くの重要なツイートが届いた場合における状況に応じて上限を柔軟に変更する仕組みを提案することが挙げられる．
文献[1] MACSKASSY, Sofus A.; MICHELSON, Matthew. Why dopeople retweet? anti-homophily wins the day!. In: Fifth International AAAI Conference on Weblogs and Social Media.
2011.
[2] UYSAL, Ibrahim; CROFT, W. Bruce. User oriented tweet
ranking: a filtering approach to microblogs. In: Proceedingsof the 20th ACM international conference on Informationand knowledge management. ACM, 2011. p. 2261-2264.
[3] PENG, Huan-Kai, et al. Retweet modeling using conditionalrandom fields. In: Data Mining Workshops (ICDMW), 2011
IEEE 11th International Conference on. IEEE, 2011. p. 336343.
[4] MARCHETTI-SPACCAMELA, Alberto; VERCELLIS,Carlo. Stochastic on-line knapsack problems. Mathematical
Programming, 1995, 68.1-3: 73-104.
[5] IWAMA, Kazuo; TAKETOMI, Shiro. Removable online
knapsack problems. In: Automata, Languages and Programming. Springer Berlin Heidelberg, 2002. p. 293-305.
[6] CHAKRABARTY, Deeparnab; ZHOU, Yunhong; LUKOSE,Rajan. Online Knapsack Problems.
[7] KELLERER, Hans; PFERSCHY, Ulrich; PISINGER,David. Knapsack problems. Springer, 2004. p.444.