ランダムな要求に対するκ-server問題の計算複雑性
スポンサーリンク
概要
- 論文の詳細を見る
本研究では,オンラインアルゴリズムを扱うモデルとしてよく知られているκ-server問題を二人ゼロ和ゲームとして扱う.κ-serer問題を,最適戦略に関して様々な結果が知られている別のゲーム(Mean Payoff Game)に変換することにより,κ-server問題の最適戦略の存在性とその計算複雑性について考察を行なった.結果として,κ-server問題には純粋最適戦略が存在することを示した.計算複雑性に関しては,我々の最適戦略を計算する方法では指数時間かつ指数領域かかることがわかった.
- 社団法人電子情報通信学会の論文
- 1996-07-25
著者
-
櫻井 幸一
九州大学大学院システム情報科学研究院
-
櫻井 幸一
九州大学大学院 システム情報科学研究科 情報工学専攻
-
山家 明男
九州大学大学院システム情報科学研究科
-
山家 明男
九州大学大学院 システム情報科学研究科 情報工学専攻
-
櫻井 幸一
九州大学大学院 システム情報科学府
関連論文
- 出力VHDLコードに透かしを埋め込むCADツールの不正コピー検知方式
- ACM CCS2007会議ならびに併設ワークショップ参加報告(セッションA-5:法律と社会,報告)
- Information Security Conference (ISC)/International Workshop for Applied PKI (IWAP)/Secure Mobile Ad-hoc Networks and Sensors (MADNES)参加報告(セッション2)
- 公開鍵暗号基盤における匿名バイオメトリクスを用いた秘密鍵管理の提案
- ダークネット観測データに基づく攻撃挙動の特徴抽出に関する考察
- DynaAO:共有ライブラリとの接点に着目したAOPを用いたプログラムの振る舞い解析(セッション5-B:セキュアプロトコルとセキュアソフトウェア開発)
- DynaAO : 共有ライブラリとの接点に着目したAOPを用いたプログラムの振る舞い解析(セッション5-B:セキュアプロトコルとセキュアソフトウェア開発)
- パケット生存時間を用いた確率的パケットマーキングによるIPトレースバック手法の提案
- ACM CCS2008会議ならびに併設ワークショップ参加報告(セッション1-A:セキュアファイルシステムと報告)
- 結託攻撃に耐性のある3分木型Subset Difference法
- 第2回PKI研究ワークショップ参加報告
- 認証局の統合と分散の定式化とその考察
- 中国語迷惑メールにおけるベイジアンフィルタの適用と評価(セッション3)
- ベイジアンフィルタリングを用いた迷惑メール対策における多言語環境でのコーパス分離手法の提案と評価(ネットワークセキュリティ, 多様な社会的責任を担うコンピュータセキュリティ技術)
- チャレンジ-レスポンスとベイジアンフィルタリングを併用した迷惑メール対策の提案(ネットワークセキュリティ)(プライバシを保護するコンピュータセキュリティ技術)
- チャレンジ-レスポンスとベイジアンフィルタの併用によるエラーメールを装った迷惑メールの検出精度の評価
- UC frameworkにおけるfunctionalityの合成について(情報通信基礎サブソサイエティ合同研究会)
- 2冪算における直接計算法を用いたマルチスカラー倍算の効率性評価
- XTRに対するサイドチャネル攻撃と効率的な対策方式
- XTRに対するサイドチャネル攻撃と致率的な対策方式
- 暗号に利用可能なモンゴメリ型楕円曲線の存在数に関する一考察(数論アルゴリズムとその応用,その1)
- 有限体F_上の超楕円曲線暗号のソフトウェア実装 (代数曲線とその応用論文小特集)
- 票数2の超楕円曲線暗号のソフトウエア実装
- 非超特異型楕円曲線上の暗号系の新たな利点について
- 一般秘匿性ポリシの束モデル
- 攻撃の時系列的諸局面に対応したセキュリティ対策の探索(セッション3-C:セキュリティ対策)
- 侵入の検知を契機にサーバを安全な状態に回復する機構(セキュリティ)
- テキストと画像情報用いた画像スパムフィルタリングの設計と評価(セッションB-10:spam,フィルタリング)
- 無線通信における物理レイヤ/MACレイヤへのDoS攻撃に耐性を有する整合フィルタを用いた符号化方式
- ACM CCS2007会議ならびに併設ワークショップ参加報告(セッションA-5:法律と社会,報告)
- ACM CCS2008会議ならびに併設ワークショップ参加報告(セッション1-A:セキュアファイルシステムと報告)
- 公開鍵暗号基盤における匿名バイオメトリクスを用いた秘密鍵管理の提案
- 公開鍵暗号基盤における匿名バイオメトリクスを用いた秘密鍵管理の提案
- IPアドレスデータベースと確率的バケットマーキングを用いたパケットフィルタリング機構の設計
- 内容の類似性を用いたトラックバックスパム判別法の評価と考察
- 内容の類似性を用いたトラックバックスパム判別法の評価と考察
- 機器認証DRMシステムの設計
- 機器認証DRMシステムの設計
- デバイス固有値を用いた対称暗号技術によるIDベース暗号化方式の実現(情報通信基礎サブソサイエティ合同研究会)
- デバイス固有値を用いた対称暗号技術によるIDベース暗号化方式の実現(情報通信基礎サブソサイエティ合同研究会)
- デバイス固有値を用いた対称暗号技術によるIDベース暗号化方式の実現(情報通信基礎サブソサイエティ合同研究会)
- IPアドレスデータベースと確率的パケットマーキングを用いたパケットフィルタリング機構の設計
- IPアドレスデータベースと確率的パケットマーキングを用いたパケットフィルタリング機構の設計
- カオスベース画像スクランブル暗号への効果的攻撃(一般:情報通信基礎サブソサイエティ合同研究会)
- カオスベース画像スクランブル暗号への効果的攻撃(一般:情報通信基礎サブソサイエティ合同研究会)
- カオスベース画像スクランブル暗号への効果的攻撃(一般:情報通信基礎サブソサイエティ合同研究会)
- パケット生存時間を用いた確率的パケットマーキングによるIPトレースバック手法の提案
- パケット生存時間を用いた確率的パケットマーキングによるIPトレースバック手法の提案
- A-7-20 パストランジスタを用いたDES S-boxの実装評価
- 出力VHDLコードに透かしを埋め込むCADツールの不正コピー検知方式
- ネットワークトポロジを考慮した効率的なマルチキャスト暗号方式
- ネットワークトポロジを考慮した効率的なマルチキャスト暗号方式
- オンライン・ショッピングにおける民事的紛争解決に関する提案
- オンライン・ショッピングにおける民事的紛争解決に関する提案
- オンライン・ショッピングにおける民事的紛争解決に関する提案
- クラウドコンピューティングにおけるセキュリティ研究動向
- A-7-25 Security Problems in Existing Privacy-preserving K-means Clustering Schemes
- プライバシー保護した相関ルールマイニングに関する再考
- プライバシー保護した相関ルールマイニングに関する再考
- プライバシー保護した相関ルールマイニングに関する再考
- システムコールの発行履歴が表す情報量の機微に基づく異常検知手法
- システムコールの発行履歴が表す情報量の機微に基づく異常検知手法
- システムコールの発行履歴が表す情報量の機微に基づく異常検知手法
- システムコールの発行履歴が表す情報量の機微に基づく異常検知手法
- e-Forensics 2008参加報告
- 複数の機密画像を埋め込み可能なグラフタイプ視覚復号型秘密分散方式の拡張(21世紀のコンピュータセキュリティ技術)
- 属性情報開示における公平性について
- 著作権保護のためのウェーブレット変換を用いた電子透かし方式の安全性評価
- 周波数変換に基づいた電子透かし技術の画質評価に関して
- 内容の類似性を用いたトラックバックスパム判別
- パケットフィルタポリシーの安全性解析と対策(研究速報,通信技術の未来を拓く学生論文)
- デジタル署名標準・メッセージ回復型エルガマル署名に対する部分ブラインドプロトコルの設計と解析
- ロール・ポリシーに基づくドキュメントアクセス制御モデル
- 初期値を考慮した共通鍵暗号操作モードの証明可能安全性
- SudanのReed-Solomon符号復号アルゴリズムを使ったブロック暗号の補間攻撃
- ブロック暗号における秘密鍵の平文ブロックのマスクについて2-key XCBCによるMAC生成スキームの安全性
- ブロック暗号における秘密鍵の平文ブロックのマスクについて : 2-key XCBCによるMAC生成スキームの安全性
- IDベース暗号、バイオメトリック認証における失効問題についての比較
- IDベース暗号、バイオメトリック認証における失効問題についての比較
- IDベース暗号、バイオメトリック認証における失効問題についての比較
- DHCPによって管理されたセグメントに存在する未使用IPアドレスの監視手法
- 改ざん位置検出用電子透かしに関する考案と提案
- 認証局と販売者の共謀攻撃に対して安全な匿名消費者-販売者透かし方式
- 認証局と販売者の共謀攻撃に対して安全な匿名消費者-販売者透かし方式
- 認証局に対する信頼仮定を排除した匿名販売者-消費者透かし方式
- IPアドレスデータベースと確率的パケットマーキングを用いたパケットフィルタリング機構の設計
- プライバシー保護した分散的ドキュメントクラスタリング
- プライバシー保護した分散的ドキュメントクラスタリング
- A-7-8 チェビシェフ多項式を利用したストリーム暗号に対する記号力学攻撃
- A-7-1 カオス・ストリーム暗号に対する記号力学攻撃の改良
- 第2回PKI研究ワークショップ参加報告
- 認証局の統合と分散の定式化とその考察
- オンライン・ショッピングにおける民事的紛争解決に関する提案
- オンライン・ショッピングにおける民事的紛争解決に関する提案
- IEEE802.11i 4 Way HandshakeプロトコルをDoS攻撃から保護する整合フィルタを用いた符号化方式
- セキュリティ対策の統合評価における個々の対策についての評価技法の提案
- IEEE802.11i 4 Way HandshakeプロトコルをDoS攻撃から保護する整合フィルタを用いた符号化方式
- セキュリティ対策の統合評価における個々の対策についての評価技法の提案
- 情報セキュリティ対策の評価技法についての考察
- オンライン先読みページングゲームにおける最適戦略の設計と解析(計算理論とその応用)