組合せオークションの勝者決定問題に対する並列分枝限定解法(EVA-2:ネットワークアプリケーションの評価,2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
スポンサーリンク
概要
- 論文の詳細を見る
次世代のオークションとして注目を集める組合せオークションの勝者決定問題はNP困難な問題である。問題の厳密解は重要な意義をもつが、分枝限定法では高速かつ高精度な上界の計算法は知られておらず短時間に解ける問題の規模が限定されてしまう。本研究では分枝限定法では対応できない問題を並列分枝限定解法を用いて高速に解くことを目的とし、1)データ構造の軽量化による分枝限定法の高速化、2)P2P通信モデルを採用した並列化をおこなった。また、提案手法のプロトタイプシステムを構築し評価をおこなった。結果として提案手法は、従来のマスター・ワーカモデルと比較して安定して良い性能を得ることができた。
- 一般社団法人情報処理学会の論文
- 2003-08-06
著者
-
藤田 聡
広島大学大学院工学研究科情報工学専攻
-
田頭 茂明
広島大学大学院工学研究科情報工学専攻
-
水戸 将弥
広島大学大学院工学研究科
-
Fujita Satoshi
Department Of Mechanical Engineering Tokyo Denki University
-
藤田 聡
広島大学大学院工学研究科
関連論文
- P2Pファイル共有システムにおける効率的なインデックスキャッシュ手法(IPv6,P2P,NGN,VoIP,FMC,コンテンツ配信,IPv6及び一般)
- メモリ制限のあるP2P DHT上の連言検索手法 (情報ネットワーク)
- 確率的な遷移を含んだ部分観測マルコフ決定過程における強化学習法
- 無線LAN環境における主成分分析を用いたハイブリッド位置推定手法(ユビキタス・モバイル,システム開発論文)
- 無線LAN位置推定システムにおける正準相関分析を用いたデバイス適応手法(ユビキタス・モバイル,システム開発論文)
- Minority Gameを利用した輻輳制御手法の評価
- 階層型P2Pを用いたセンサ情報の広域共有方式 (情報ネットワーク)
- ネットワーク再構成を用いたインタレストマイニング法の改良(IPv6,P2P,NGN,VoIP,FMC,コンテンツ配信,IPv6及び一般)
- BitTorrent型並列ダウンロードシステムにおける効率的なマッチメーキング手法の提案(コンテンツ配信)
- グループの動的形成に基づく無線LANのための適応的メディアアクセス制御手法(MAC,4Gに向けたモバイルマルチメディア,モバイル通信品質,モバイルコンテンツマネジメント,モバイルセキュリティ)
- ノードの近接性を考慮したP2P DHTの構築手法(ルーチング,ネットワーク制御,QoS,ルーチング,マルチキャスト及び一般)
- ベンディング法を用いたセンサネットワークのためのナビゲーション手法(ユビキタスネットワーキング,ネットワーク制御,QoS,ルーチング,マルチキャスト及び一般)
- ベンディング法を用いたセンサネットワークのためのナビゲーション手法
- 分散ハッシュテーブル型P2Pシステムにおけるブルームフィルタを用いた高速連言検索手法の評価(2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)
- ノードのFree Degreeに基づいたMANETのための適応的ルーティングプロトコルの評価(2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)
- DARTを用いたアドホックネットワークのアドレス空間均等化手法(OS-1 : ネットワーク,2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)-研究会・連続同時開催-)
- PeerCQにおける効率的な条件付き情報監視手法(OS-1 : ネットワーク,2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)-研究会・連続同時開催-)
- パッシブ型RFIDを用いた方向検出システム(MoMuC研セッション,超高速モバイル通信時代のマルチメディアアプリケーション及び一般)
- A Fault-Tolerant Content Addressable Network(Networks)
- 分散ネットワーク上の故障診断問題について(新世代の計算限界-その解明と打破-招待解説論文)
- P2P環境における機能並列性に着目した分枝限定法の評価
- アドホックネットワークのためのQ-routing Protocolの性能評価
- Distributed Zone Partitioning Schemes for CAN and Its Application to the Load Balancing in Pure P2P Systems (特集 新時代の分散処理とネットワーク(WebサービスとP2P))
- 無線伝送路の可逆性を用いた小型携帯端末のための共有情報生成方式の提案(DPS/MBL合同セッション センサネットワーク)
- 無線メッシュネットワーク上の測位システムにおける観測データ集約による通信量削減手法の提案(モバイルコンピューティング、モバイルアプリケーション、ユビキタス通信、モバイルマルチメディア通信及び一般)
- マルチパスの伝送路特性に基づく共有情報生成方式の認証への応用(学生セッション)
- 無線メッシュネットワークにおける端末位置推定のためのチャネル割当方式の提案(学生セッション)
- Twitter分析に基づく位置依存文字列の抽出
- Twitterにおけるコンテキストと単語の相関関係分析
- Twitterにおけるコンテキストと単語の相関関係分析
- Twitterにおけるコンテキストと単語の相関関係分析
- Twitterにおけるコンテキストと単語の相関関係分析
- B-15-25 メッシュネットワーク上での位置推定のための通信量削減手法(B-15.モバイルマルチメディア通信,一般セッション)
- 組合せオｰクションの勝者決定問題に対する分枝限定解法の機能並列化手法
- 組合せオークションの勝者決定問題に対する分枝限定解法の機能並列化手法(性能評価環境と応用)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 組合せオークションの勝者決定問題に対する並列分枝限定解法(EVA-2:ネットワークアプリケーションの評価,2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- 組合せオークションの勝者決定問題に対する発見的解法
- ユーザからの非明示的な要求の獲得手法の提案とその勤務表作成問題への応用
- ユーザからの非明示的な要求の獲得手法の提案とその勤務表作成問題への応用
- 知識概念に着目したユーザの分類に基づくパーソナライズドWeb検索システムの提案
- 知識概念に着目したユーザの分類に基づくパーソナライズドWeb検索システムの提案
- 知識概念に着目したユーザの分類に基づくパーソナライズドWeb検索システムの提案
- 無線LANの指向性アンテナを利用した被写体方向推定の検討
- 無線LANの指向性アンテナを利用した被写体方向推定の検討
- 近距離無線環境のためのローカルクラウドストレージの提案(ブロードバンドアクセス,ホームネットワーク,ネットワークサービス,通信利用アプリケーション,一般)
- 最悪性能比が2.7834二次元調和算法の提案と評価
- The Distributed Anonymous Resource Conflict Resolution Problem
- メモリ制限のあるP2P DHT上の連言検索手法(P2P,コンテンツ配信,コンテンツ配信,コンテキストアウェアネス,IPv6,認証,ID/名前管理及び一般)
- 小型乗合バスシステムにおける最適発車間隔問題のモデル化とその強化学習による獲得手法の提案
- クーポン収集方式に基づくデマンドバススケジューラの設計と評価
- 負例に着目した嗜好解析手法の提案とそのフィードリーダーへの応用
- 知識概念に着目したユーザの分類に基づくパーソナライズドWeb検索システムの提案
- 負例に着目した嗜好解析手法の提案とそのフィードリーダーへの応用
- 負例に着目した嗜好解析手法の提案とそのフィードリーダーへの応用
- 負例に着目した嗜好解析手法の提案とそのフィードリーダーへの応用
- 負例に着目した嗜好解析手法の提案とそのフィードリーダーへの応用
- 検索サマリの流通によるP2P上の情報共有の効率化(P2P,コンテンツ配信,コンテキストアウェアネス,IPv6,認証,ID/名前管理及び一般)
- 階層型P2Pを用いたセンサ情報の広域共有方式(P2P,コンテンツ配信,コンテキストアウェアネス,IPv6,認証,ID/名前管理及び一般)
- 偏りのあるインデックス配布手法とP2Pファイル検索への応用(P2P,コンテンツ配信,コンテンツ配信,コンテキストアウェアネス,IPv6,認証,ID/名前管理及び一般)
- パッシブ型RFIDを用いた方向検出システム(MoMuC研セッション,超高速モバイル通信時代のマルチメディアアプリケーション及び一般)
- コンテキスト情報を用いた適応的な無線ネットワーク選択手法の提案 (アドホックネットワーク)
- 並列プログラムの並列度を自律的に制御するアクティブスケジューラの実装と評価
- ピュア型P2Pシステムにおける匿名インデックス検索方式(2003年並列/分散/協調処理に関する「松江」サマーワークショップ(SWoPP松江2003))(CPSY-2情報管理)
- P2Pシステム上でのリザルトキャッシングを用いた条件付検索手法(ブロードバンドサービス,CDN/P2P/Gridなどのオーバレイネットワーキング技術及び一般)
- グラフの支配集合間の相互変換可能性について
- コンテキストアウェアIMEの実現へ向けた動的辞書生成手法の提案
- Twitterを用いたコンテキストと入力文字列の相関関係分析
- B-15-14 無線LANを用いた位置推定における観測データ補正手法の提案(B-15.モバイルマルチメデイア通信,一般セッション)
- B-15-13 無線LANを用いた位置推定における学習データ補間手法(B-15.モバイルマルチメデイア通信,一般セッション)
- B-6-57 移動シンクを利用した無線センサネットワークにおける許容遅延時間を考慮したデータ収集方式(B-6.ネットワークシステム,一般セッション)
- 複数端末の協調による自動的な設定切り換え手法に関する一検討
- 複数端末の協調による自動的な設定切り換え手法に関する一検討
- コンテキスト情報を用いた適応的な無線ネットワーク選択手法の提案
- コンテキスト情報を用いた適応的な無線ネットワーク選択手法の提案
- 許容遅延時間を考慮した省電カなセンサデータ収集方式
- 伝送路可逆性を用いた小型端末向け秘密鍵生成方式における堅牢性の検証
- UDPブロードキャストを用いた高信頼性データ通信プロトコルの実装と評価
- 平均乗車時間を最小にする路線バスの運行経路決定方式の提案と評価
- 無線LANを用いた位置推定における学習コスト削減のためのデータ補間手法の提案
- トンネル施工現場における無線LAN位置推定のための精度改善手法の提案
- 無線LANを用いた位置推定における学習コスト削減のためのデータ補間手法の提案
- メモリ制限のあるP2P DHT上の連言検索手法
- ピュア型P2Pシステムにおける負荷分散を考慮したCAN構成法(2003年並列/分散/協調処理に関する「松江」サマーワークショップ(SWoPP松江2003))(CPSY-2情報管理)
- FTS2000-23 クラッシュトレラントな動的プロセッサ集合操作プロトコル
- 無線センサネットワーク上の低遅延な耐故障ルーティングアルゴリズム(モバイルユビキタス/センサ技術,アドホックネットワーク,RFID,一般及び技術展示)
- 階層型ピア・ツー・ピアファイル共有システムのためのタイムラインベースドなクエリ駆動キャツシュプロトコル(トラヒック計測・制御,ポリシー管理,ネットワーク異常検知,信頼性,認証,ID/名前空間,ネットワークセキュリティ,プライバシー,VPN,DDoS及び一般)
- 無線センサネットワークを利用した位置測位システムの構築(性能評価環境と応用)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 周辺情報検索におけるプロキシシステムのためのキャッシュ置換アルゴリズム(モバイルコンピューティング)
- 周辺情報獲得のためのプロキシキャッシュシステム(EVA-2:ネットワークアプリケーションの評価,2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- Content-Addressable Networkにおける効率的なキャッシング手法の提案
- P2P型サービスのための協調的な動的ユーザ管理システム(トラヒック計測・制御,ポリシー管理,ネットワーク異常検知,信頼性,認証,ID/名前空間,ネットワークセキュリティ,プライバシー,VPN,DDoS及び一般)
- コーラムコンセンサスを用いた分散相互排除命令ライブラリの設計と評価
- デマンドバスシステムのための最適経路選択法の実装とそのオンライン配車システムへの応用
- デマンドバスシステムのための最適経路選択法の実装とそのオンライン配車システムへの応用
- 転送遅延を考慮したWMN上のアクセスポイント削減手法 (コミュニケーションクオリティ)
- マルチプロセッサスケジューラHMSSの標準タスクグラフセットSTGを用いた性能評価(EVA-2:並列処理と評価)
- インスタンスの進化に基づくTSPのための発見的解法の改良
- P2Pライブストリーミングのための離脱耐性のある課税スキーム(映像/音声サービスの品質,メディア品質,ネットワークの品質・QoS制御,次世代/新世代ネットワークアーキテクチャ,超臨場感コミュニケーション,信頼性,一般)
- リンケージ同定を導入したTSPのための進化計算解法の提案
- 転送遅延を考慮したWMN上のアクセスポイント削減手法(映像/音声サービスの品質,メディア品質,ネットワークの品質・QoS制御,次世代/新世代ネットワークアーキテクチャ,超臨場感コミュニケーション,信頼性,一般)