Pseudo Expectation : A Tool for Analyzing Local Search Algorithms
スポンサーリンク
概要
- 論文の詳細を見る
Watanabe et al. [Lecture Notes in Comp. Sci. 2827 (2004), 50] proposed pseudo expectation for analyzing relatively simple Markov processes that can be often seen as simple execution models of local search algorithms. In this paper, we first explain how it is used, and then investigate the approximation error bound of pseudo expectations.
- 理論物理学刊行会の論文
- 2005-04-30
著者
-
渡辺 治
東京工業大学情報理工学研究科数理・計算科学専攻
-
渡辺 治
東工大情報理工
-
WATANABE Osamu
Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology
-
渡辺 治
東京工業大学工学部情報工学科
-
Watanabe Osamu
Dept. Computer Science Tokyo Institute Of Technology
関連論文
- 5.理論研究の役割(情報処理技術の未来地図,50周年記念特集号)
- 20aEA-10 疎なランダム行列の第1固有値に関するcavity解析(20aEA 情報統計力学,領域11(統計力学,物性基礎論,応用数学,力学,流体物理))
- ハッシュ関数の認証プロトコルへの応用
- 3充足可能性判定問題3SATの正例題生成手法の解析(並列処理)
- 3充足可能性判定問題3SATの正例題生成手法について
- 方位選択性問題への理論計算機科学からのアプローチ (離散的アルゴリズムと計算量)
- 百行プログラミングの試み : 情報通信技術の科学的理解のために(科学的リテラシー)
- 最大尤度解探索の計算複雑さ
- NP困難問題における最悪時困難性からの平均時困難性証明への試み
- 教養としてのコンピュータ・サイエンス教育 : 東京工業大学での試み
- メッセージ伝播法によるグラフの分割アルゴリズム
- Pseudo Expectation : A Tool for Analyzing Local Search Algorithms
- 単純な規則で表わされるマルコフ過程の近似解析手法
- LDPC符号に対するランダム復号法の解析
- A-17 On the Influence of Outliers in the Soft Margin SVM Framework
- ブースティング技法のアルゴリズム的考察
- サポートベクトルマシンにおける例外の影響力の定め方について
- 相対化計算の元でのクラスの等価性についての一考察
- 相対化計算の元でのクラスの等価性についての一考察
- Provably Fast Training Algorithms for Support Vector Machines
- TD-1-4 サンプリング技法でエラーを抽出する方法について
- An Improved Randomized Algorithm for 3-SAT (New Developments of Theory of Computation and Algorithms)
- Groverの量子探索アルゴリズムの決定性運用法について
- モノポリストゲームのゲーム長(手数)について
- 計算を究める : アルゴリズムと計算複雑さの研究 : 情報処理技術 : 過去十年そして今後の十年
- 25pQK-12 正解が埋め込まれたグラフ等分割問題の統計力学的解析(ネットワーク一般・情報統計力学,領域11,統計力学,物性基礎論,応用数学,力学,流体物理)
- MAX-2SAT問題の平均時間計算量の解析
- MAX-2SAT問題の平均時間計算量の解析
- A Message Passing Algorithm for MAX2SAT(New Trends in Theory of Computation and Algorithm)
- 弱いランダム仮定の元での公開鍵暗号の強秘匿性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- A_009 An Improved Upper Bound for the Three Domatic Number Problem
- 電子情報通信と離散数学(電子情報通信と数学)
- 計算の複雑さの平均的な解析について(計算量理論の諸相 : その基礎的研究)
- 情報セキュリティ技術と計算の複雑さの理論 (特集 暗号化とセキュリティ--アルゴリズムとプロトコル)
- NP型探索問題のテスト例生成問題について
- NP型問題の近似解法の可能性について
- 計算論的学習理論のお話
- 一方向関数のお話し
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- TK-7-5 グローバルCOE報告 : 計算世界観の深化と展開(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
- 超平面ハッシュ関数に基づく分散A* アルゴリズムの提案と多重配列アラインメント問題への応用
- 計算論から見たランダムネス (特集 予測と発見)
- 確率的情報処理と統計力学--様々なアプローチとそのチュートリアル(7)乱択アルゴリズムへの招待
- r-of-k閾値関数に対するブースティングを用いた学習
- マルコフ過程の近似解析と乱択アルゴリズムの解析への応用
- 平均計算時間に基づく計算複雑さの研究について(計算量理論とその周辺)
- 確率的アルゴリズムにおける効率・正解率間のトレードオフ関係について
- 6. 確率的アルゴリズム (アルゴリズムの最近の動向)
- On Reliability and Efficiency of Probabilistic Algorithms (形式言語理論とオ-トマトン理論)
- A Derivation of Cook's Simulation Algorithm by Program Transformation (Studies on Computational Complexities and Related Topics)
- DS-1-7 On Coppersmith's Technique and its Limit
- On Polynomial Time Many-One Completeness of One-Way Functions : Preliminary Report
- 計算複雑さの理論 : 我々は何を研究しているのか?
- Spectral Analysis of Random Sparse Matrices
- The Relation between Time and Accepting Probability on Probabilistic Simple Decision Trees : Extended abstract(Mathematical Theories on Computing Schemes and Their Applications)
- A planted solution model for the MAX-2SAT problem (情報物理学の数学的構造--RIMS研究集会報告集)
- でたらめさを利用した計算--「乱択アルゴリズム」の世界 (特集 計算とは何か)
- DS-1-6 A Message Passing Algorithm for MAX2SAT
- 計算複雑さの研究って?
- NP-解探索における質問計算量について
- An O(n^)-Space and Polynomial-Time Algorithm for Directed Planar Reachability