仕事に対するエージェント集合割り当て問題の近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
分散計算問題の定式化の一つとして,仕事に対するエージェント集合割り当て問題(Task-Coalition Assignment Problem,以下TCAP)がある.TCAPでは,エージェントと仕事がそれぞれ複数与えられ,仕事をエージェント集合が処理することによって利益が得られる.この利益を最大化するエージェントの部分集合と仕事の組み合せを求めるのが目的である. 本稿ではまず,TCAPを厳密に定義する.そして最大クリーク問題がTCAPの特別な場合であることを示すことにより,P=NPでない限り最適解の値と近似解の値の比が定数であるような多項式時間アルゴリズムが存在しないことを証明する.次に,実用的なTCAPのサブクラスである1-TCAPを定義する.1-TCAPではエージェントと仕事がスカラー量で特徴づけられる.本稿では1-TCAPに対する近似アルゴリズムを示し,最適解の値と近似解の値の比が最悪の場合でも3以下であることを証明する.
- 社団法人電子情報通信学会の論文
- 1999-12-10
著者
関連論文
- 移動センサノードを用いたデータ収集型WSNでのk重被覆時間の最大化手法
- ユーザ指定関係に基づいた情報保存を満たすXMLスキーマ進化
- 木埋め込み関係に基づくXMLスキーマ進化に応じたXPath問合せ変換(夏のデータベースワークショップ2007(データ工学,一般))
- 木の埋め込み関係に基づくXMLスキーマ進化に応じた文書変換器の生成法(夏のデータベースワークショップ2007(データ工学,一般))
- 木埋め込み関係に基づくXMLスキーマ進化に応じたXPath問合せ変換(XML (1),夏のデータベースワークショップ2007(データ工学,一般))
- 木の埋め込み関係に基づくXMLスキーマ進化に応じた文書変換器の生成法(XML (1),夏のデータベースワークショップ2007(データ工学,一般))
- XMLデータベースにおけるスキーマ進化のための更新操作群とそれらのスキーマ表現能力保存に関する性質(基礎理論,フォーマルアプローチ論文)
- XMLデータベースへの型推論を用いた攻撃に対する安全性検証(XML,夏のデータベースワークショップDBWS 2006)
- XMLデータベースへの型推論を用いた攻撃に対する安全性検証(XML)
- 系統的なテストを可能にするユビキタスアプリケーションシミュレータの提案(UBI6:プラットフォーム・アーキテクチャ)
- 指向性アンテナおよび車車間通信を用いた歩行者位置追跡手法とその評価(セッション2)
- 分離・合流をともなうグループ観光スケジュール作成機能の提案
- 分離・合流を伴うグループ観光スケジュール作成機能の提案(セッション4)
- MANETによる携帯端末でのワンセグ視聴品質向上手法(セッション6-C:無線ネットワークと応用技術)
- 多数の観光候補地から効率良い観光スケジュールを自動的に作成・提案するシステムP-TourのGoogle Mapsを利用した設計と実装(セッションB-9:マルチメディア,アプリケーション)
- P-Tour : 観光スケジュール作成支援とスケジュールに沿った経路案内を行うパーソナルナビゲーションシステム(ITS)(次世代移動体通信システム)
- 車車間通信による交差点鳥瞰映像ストリーミング手法の提案(セッション2)
- 各車両の予定経路情報を利用した車車間通信による情報取得手法の提案(セッション1)
- メッセージフェリーと車車間通信を併用した渋滞情報収集システムの情報伝播効率の改善(車車間通信技術,次世代社会基盤をもたらす高度交通システムとモバイル通信システム)
- 多数の情報家電を仮想空間を介して遠隔操作するフレームワークの提案(UBI-1【ホームネットワーク/実世界インタフェース】)
- 仮想空間を用いたスマートスペースアプリケーション向けシミュレータ(モバイルコンピューティング,情報洪水時代のネットワークサービス)
- 異なる品質要求を持つ複数ユーザへのピアツーピアビデオ配信手法(ネットワークプロトコル,情報洪水時代のネットワークサービス)
- ハードウェア化のための多目的GAアーキテクチャの提案(バイオインフォマティックスの情報科学への応用)
- 携帯無線端末向け複数ビデオ同時視聴サービスのための放送型ビデオ配信方式(セッション3:ユビキタスシステムとマルチメディア通信)
- 将来の混雑状況予測に基づく混雑回避巡回スケジューリング手法の提案(セッション4)
- MANET上での効率良いビデオ配信を目的とした準最適マルチキャスト配送木の分散構築法(無線・モバイルネットワーク,シームレスコンピューティングとその応用技術)
- FPGA上への遺伝的アルゴリズムの柔軟な実装手法の提案(応用技術,リコンフィギャラブルシステム論文)
- 代数的仕様からのドュメント自動生成について
- 抽象的順序機械型代数的仕様からのドキュメント生成システム
- 抽象的順序機械型代数的仕様からのドキュメント生成システムの試作
- XMLデータベースへの推論攻撃による機密情報特定可能性の形式化とある前提条件のもとでの特定可能性検証法の提案
- XMLデｰタベｰスにおける表現能力を保存したスキｰマ更新操作
- XMLデータベースにおける表現能力を保存したスキーマ更新操作(Web,XML,文書検索)(データ工学,ディペンダビリティ,一般)
- XMLデータのスキーマ統合のための枠組の提案
- 異なる構造を持つXMLデータを統合するための構造間の関係について(実空間とサイバースペースの融合 : 感性, データベース, ロボティクスおよび一般)
- 関連性の高いアイテム集合のマイニングに要する計算量
- 検索および再帰なし無閉路スキーマに対する型検査問題の計算量
- オブジェクト指向データベースにおける推論攻撃不可能性の逐次的検査法
- 満足度と体力を考慮した観光スケジューリング法の提案
- 「情報処理学会論文誌:数理モデル化と応用」の編集にあたって
- 評価者間類似度計算の改善による汚染コンテンツダウンロード抑制効果向上
- 携帯電話端末への低コスト動画広告配信を目的としたWiFi併用協調ダウンロード方式
- 都市や観光地における混雑状況を考慮した多数ユーザ同時巡回スケジューリング手法
- The validity problem of positive XPath queries in the presence of DTDs (ソフトウェアサイエンス)
- データサイズと送信期限を考慮したDTN経路制御手法
- 無線センサネットワーク長寿命化のためのノード集合の分割に基づくスリープスケジューリング手法
- 無線センサネットワーク長寿命化のためのノード集合の分割に基づくスリープスケジューリング手法
- 天気変化を考慮した観光スケジュール群の探索アルゴリズム
- 電子トリアージタグに基づいた傷病者搬送計画システムの提案
- 利用者の状況に応じて画面レイアウトが変更可能な遠隔教育支援システムの提案
- 大容量コンテンツ配信を目的とした携帯電話網・Bluetooth併用協調ダウンロード手法
- 検索処理を高速化するためのデータベーススキーマの設計手法
- 文字列集合における識別文字列を求めるための多項式時間手続き
- 多数の観光候補地から効率良い観光スケジュールを自動的に作成・提案するシステムP-TourのGoogle Mapsを利用した設計と実装(セッションB-9:マルチメディア,アプリケーション)
- モバイルアンカノードを用いた低コストな水中センサノードの位置推定法
- 移動センサノードを用いたデータ収集型WSNでのk重被覆時間の最大化手法
- 水面を移動可能なアンカーノードを用いた水中センサネットワークのノード位置推定手法の提案
- 編集にあたって(平成20年度論文賞の受賞論文紹介)
- 電子トリアージタグに基づいた傷病者搬送計画システムの提案
- 天気変化を考慮した観光スケジュール群の探索アルゴリズム
- 自然語仕様から代数的仕様への変換における表現式の構文規則の生成
- メソッドスキーマにおける型整合性の解析アルゴリズム
- メソッドスキーマの型整合性の十分条件
- 自然語仕様から代数的仕様への変換における辞書項目生成の支援
- 通信プロトコルの自然語仕様から代数的仕様への変換における文章間の依存関係の解析
- 大容量コンテンツ配信を目的とした携帯電話網・Bluetooth 併用協調ダウンロード手法
- 複数日にわたる観光のためのパーソナルナビゲーションシステム(モバイルアプリケーション,ユビキタス時代を支えるモバイル通信と高度交通システム)
- 宿泊地を考慮した観光スケジュール作成支援機能の提案(交通における計測・一般(電気系3学会ITS合同研究会))
- 宿泊地を考慮した観光スケジュール作成支援機能の提案(交通における計測, 一般(電気系3学会ITS合同研究会))
- オブジェクト指向データベースにおける推論攻撃不可能性の逐次的検査法
- オブジェクト指向データベースにおける推論攻撃不可能性の逐次的検査法
- XMLスキーマで定義された型とXPath式との対応の解析手法
- ユーザ指定関係に基づいた情報保存を満たすXMLスキーマ進化
- XMLデータベースにおける表現能力を保存したスキーマ更新操作(Web,XML,文書検索)(データ工学,ディペンダビリティ,一般)
- XMLスキーマで定義された型と XPath 式との対応の解析手法
- 抽象的順序機械型代数的仕様からのドキュメント生成システム
- 空調機用マイコンソフトの形式的仕様記述と検証法について
- データマイニングに要する計算量に関する一考察
- タプル間の依存関係を表現できる確率的データベースモデルの提案
- 無閉路オブジェクト指向データベーススキーマにおける型検査問題の計算量
- オブジェクト指向データベースにおける型検査問題の計算量
- オブジェクト指向データベースにおける型検査問題の計算量
- マルチエージェント環境における時刻の前後関係に関する推論問題
- DTD存在下での否定を含まないXPathクエリの恒真性判定
- オブジェクト指向データベースにおけるインスタンスの内容に依存したアクセス権モデルの設計 (時空間データベースおよび一般)
- オブジェクト指向データベーススキーマにおけるセキュリティフロー検出の形式的手法
- オブジェクト指向データベースにおけるデータ漏洩検出問題に関する考察
- オブジェクト指向データベースにおけるアクセス権モデルの設計
- 仕事に対するエージェント集合割り当て問題の近似アルゴリズム
- 2本の時間軸間の時間的推論
- 仕事に対するエージェント集合割り当て問題の近似アルゴリズム
- オブジェクト指向データベースにおける質問のアクセス権分析
- Type Consistency Problems for Queries in Object-Oriented Databases
- オーエンス・ルイス : アンビエント環境制御を用いた知的オフィスチェアの提案(アンビエントインテリジェンス技術とその応用)
- オブジェクト指向データベースにおける質問の型検査問題
- オブジェクト指向データベースプログラムにおける型検査のアクセス制御への応用
- Combining the tractability of duplicate-free DTDs and disjunction-capsuled DTDs for XPath satisfiability with sibling axes (ソフトウェアサイエンス)
- 決定性線形トップダウン木変換器における問合せ保存の決定可能性 (ソフトウェアサイエンス)
- 兄弟軸をもつXPath充足可能性問題に対するduplicate-free DTDとdisjunction-capsuled DTDの多項式時間可解性の融合
- 決定性線形トップダウン木変換器における問合せ保存の決定可能性