文献

J-GLOBAL ID：201702284394323166   整理番号：17A1637367

オンラインナップサック問題と予算誠実な二部マッチング【Powered by NICT】

Online knapsack problem and budgeted truthful bipartite matching

著者 (1件)： Vaze Rahul (School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： INFOCOM  ページ： 1-9  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 二つの関連したオンライン問題:ナップサックと誠実な二部マッチングを考察した。これら二つの問題のために,少しであっても,利用可能な適切な頂点のどれともオンライン様式で「一致」するか到着左頂点である共通のテーマ整合端の値の和を最大化し,整合左頂点上の合計重量制約を満足させるようにした。左頂点が一様にランダム順(秘書モデル)に到着すると仮定して,二つの問題,2e競合と24競争力があることをのために提案された,それぞれ二ほぼ同様のアルゴリズム。提案したオンライン二分マッチングアルゴリズムも真実であることを示している:その入札/重量を誤入に左バーテックスの誘因ではない。これら問題の直接応用はデバイス間通信可能にしたセルラネットワークにおける協調リレーへの負荷バランシング,一般化adwords,クラウドソーシングオークション,マッチング無線ユーザを有するジョブ割り当てを含む。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： アルゴリズム ,  負荷分散 ,  *ナップサック問題 ,  *マッチング
準シソーラス用語： ワイヤレス ,  協調中継 ,  セルラーネットワーク ,  D2D ,  マッチングアルゴリズム ,  *オンライン , 【Automatic Indexing@JST】

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： オンライン ,  ナップサック問題 ,  予算 ,  マッチング