離散凸解析から見たDijkstra法
スポンサーリンク
概要
- 論文の詳細を見る
ダイクストラ法は,非負の枝長をもつ有向グラフにおける単一始点最短路問題に対する有名なアルゴリズムである.本稿では,ダイクストラ法を離散凸解析の視点から調査し,ダイクストラ法がL凹関数最大化に対する最急上昇法を実装したものと見なせることを指摘する.
- 2012-05-07
著者
-
室田 一雄
京都大学
-
室田 一雄
東京大学大学院 情報理工学系研究科
-
塩浦 昭義
東北大学大学院情報科学研究科
-
塩浦 昭義
上智大学理工学部
-
Murota Kazuo
Department Of Mathematical Informatics Graduate School Of Information Science And Technology Univers
-
室田 一雄
Department Of Mathematical Informatics Graduate School Of Information Science And Technology Univers
-
室田 一雄
東京大学大学院情報理工学系研究科
関連論文
- 1-C-2 同時特異値分解とその構造定理(つくばOR学生発表(3))
- A survey on convergence theorems of the dqds algorithm for computing singular values
- 2-B-5 誤差制御付き同時ブロック対角化手法の半正定値計画問題への応用(半正定値計画問題)
- 1-B-6 離散凸関数の錐別優加法性(離散最適化(1))
- 2次の効用関数に関する不可分財の最適配分問題の計算量について
- ヨーロピアンアジアンオプションの効率的な価格付けの手法 : AMOアルゴリズムの実装と解析の改良
- 特異値計算アルゴリズムdqds法の収束定理 (計算科学の基盤技術としての高速アルゴリズムとその周辺)
- 特異値計算アルゴリズムdqds法の理論保証付き超2次収束シフト戦略(理論)
- On Convergence of the dqds and mdLVs Algorithms for Computing Matrix Singular Values(Mathematical Sciences for Large Scale Numerical Simulations)
- Sinc-Gauss Sampling Formula(Mathematical Sciences for Large Scale Numerical Simulations)
- 特異値計算のためのdqds法とmdLVs法の収束性について(理論)
- Gauss核サンプリング公式の複素関数論による誤差評価(理論)
- 連続/離散ハイブリッドM凸関数に関する一考察
- 電気抵抗回路に基づくグラフ上の半教師付き学習機械(テーマセッション,文字認識・文書理解)
- Electric Network Kernel for Support Vector Machines(SVM)
- Electric Network Kernel for Support Vector Machines (Decision Theory and Optimization Algorithms)
- 2段階アルゴリズムによるSVMの解法
- 連続/離散ハイブリッド凸最適化とその最適性規準
- 2段階アルゴリズムによるSVMの解法 (数理最適化から見た「凸性の深み,非凸性の魅惑」)
- 半正定値計画法に対する主双対内点法の群対称性 (数理最適化の理論とアルゴリズム)
- 付値マトロイドの理論 : 多項式行列の組合せ構造
- Computing the Combinatorial Canonical Form of a Layered Mixed Matrix
- ロバスト混合整数計画に対するBenders分解法(応用)
- ロバスト混合整数計画に対するBenders分解法(離散最適化)
- 2-A-10 処理時間が制御可能なジョブをもつスケジューリング問題に対する効率的なアルゴリズム(計算と最適化(2))
- 凸費用ネットワークフロー問題の双対に対する効率的なアルゴリズムとそのコンピュータビジョンへの応用
- 離散凸最適化ソルバとデモンストレーションソフトウェアの公開
- アメリカン・アジアンオプションの価格の近似に対する計算幾何手法的アプローチ
- アメリカン・アジアンオプションの価格付けに対する計算幾何手法を用いた近似アルゴリズム(計算機科学の理論とその応用)
- ヨーロピアン・アジアンオプションの価格付けに関する近似的解法
- 2-F-10 POS分析とアンケートに基づく大学生協の食育向上の試み(大学でのOR)
- Efficient Algorithms for Location Problems on Tree Networks
- Scaling Algorithms for M-convex Function Minimization (Mathematical Optimization Theory and its Algorithm)
- M凸関数の最小化に対するスケーリングアルゴリズムとその実験的評価(組合せ)
- スケーリング技法を用いたM凸関数の最小化アルゴリズム
- Quasi M-convex Functions and Minimization Algorithms (Algorithm Engineering as a New Paradigm)
- Extension of M-convexity and L-convexity to Polyhedral Convex Functions : Extended Abstract (Continuous and Discrete Mathematics for Optimization)
- M-Convex Function on Generalized Polymatroid(Continuous and Discrete Mathematical Optimization)
- 一般化ポリマトロイド上のM凸関数(組合せ最適化(3))
- 2-C-9 リンキングシステムによるM凸関数の変換(グラフ・ネットワーク(2))
- 2-D-12 行列*代数のブロック対角化アルゴリズムと半正定値計画問題への応用(非線形計画(2))
- 組合せ最適化と凸解析(文献賞)
- 組合せ論的緩和法 : 組合せ最適化技法による代数計算(組合せ最適化)
- ポリマトロイド対の普遍基の特徴付け
- L凸関数に対する離散ヘッセ行列(離散最適化)
- M凸劣モジュラ流問題に対する容量スケーリング法
- M凸劣モジュラ流問題に対する容量スケーリングアルゴリズム(最適化(1))
- 電気抵抗回路に基づくグラフ上の半教師付き学習機械(テーマセッション,文字認識・文書理解)
- 近傍システム : アルゴリズムおよびジャンプシステムと双劣モジュラ多面体との関係
- 第14回RAMPシンポジウムルポ(情報の窓)
- A-019 2次の効用関数に関する不可分財の最適配分問題 : 計算複雑度とアルゴリズム(モデル・アルゴリズム・プログラミング,一般論文)
- 処理時間が調整可能かつ分割処理可能なジョブのスケジューリング問題に対する分割統治アプローチ
- 第1回 離散凸関数はどのような性質を満たすべきか : 離散最適化の視点から(離散最適化とその応用)
- M凸関数最小化に対する高速スケーリング算法と資源配分問題への応用
- ヨーロッパ型及び貯蓄型アジアオプションの高精度かつ高速な価格計算
- 回転変位を持つ対称構造物のブロック対角化手法〔英文〕
- 回転変位を持つ対称構造物のブロック対角化手法--理論編
- 回転変位を持つ対称構造物のブロック対角化手法--数値解析編
- 非解析的な関数を用いた変数変換型数値積分公式
- 非解析的な関数を用いた変数変換型数値積分公式について(並列数値計算アルゴリズムとその周辺)
- 最適化算法と高速自動微分法について(数値解析と科学計算)
- 高速微分法における変数消去のグラフ論的考察
- Voronoi線図を構成する逐次添加型算法の改良と諸算法の実験的比較
- 多重グラフにおける均等辺彩色を求める高速アルゴリズム
- 多変数多項式行列の構造的弱既約性と構造的可制御性判定への応用
- Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of Subdeterminants
- 多項式行列に対する組合せ論的緩和法の実現について(組合せ最適化)
- 分割行列の階層的分解(II) : 同値変換(離散数学)
- 分割行列の階層的分解(I) : 相似変換(離散数学)
- EFFICIENT STRATEGY PROOF FAIR ALLOCATION ALGORITHMS
- 2次の効用関数を持つ不可分財の最適配分問題に対する近似解法の研究 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 2次の効用関数に関する組合せオークションにおける最適配分問題のアルゴリズム
- 2-E-8 最小費用テンション問題に対する算法と画像処理への応用(離散最適化)
- "一般性"を仮定した分割行列に関する最大最小定理とDulmage-Mendelsohn型分解(組合せ最適化)
- 独立マッチングの基本構造に関する一定理(組合せ最適化)
- Rigorous Proof of Cubic Convergence for the dqds Algorithm for Singular Values
- 離散凸解析(Discrete Convex Analysis)((離散可積分系と離散解析)
- 離散凸解析 : 組合せ最適化における凸性
- 離散凸解析(最適化の数理)
- マトロイドと凸解析(最適化の数理における離散と連続構造)
- Millerの後退漸化式法再考(数値計算アルゴリズムの現状と展望II)
- F.シャトラン/伊理正夫・伊理由美訳, 行列の固有値, シュプリンガー・フェアラーク東京, 1993, 344 pp.
- A note on the dqds algorithm with Rutishauser's shift for singular values
- 粗代替性をもつ効用関数の費用制約の下での最大化
- 2-D-8 離散ヘッセ行列と凸拡張可能性に関する注意(最適化)
- Dijkstra Algorithm Viewed from Discrete Convex Analysis (コンピュテーション)
- 代用電荷法におけるスキームの「不変性」について
- 離散システムの不変な階層構造を求めて : グラフからマトロイドへ
- Applied Mathematical Series 51, 52, Singularity and Groups in Bifurcation Theory, Vol. 1, Vol. 2, Vol. 1: M. Golubitsky, D. G. Schaeffer, 1985, 463pp., / Applied Mathematical Series 51, 52, Singularity and Groups in Bifurcation Theory, Vol. 1, Vol. 2, Vol
- 数値計算技術の現状-6完-
- 数値計算技術の現状-5-
- 数値計算技術の現状-4-(講座)
- グラフの頂点価格付け問題に対する実用的近似解法 (アルゴリズムと計算理論の新展開)
- 1-D-9 半正定値離散ヘッセ行列をもつ離散非凸関数の構成(離散最適化(2))
- 離散凸解析から見たDijkstra法
- 1-C-9 離散凸解析を利用したコールセンターのシフトスケジューリング(離散最適化(1))
- 離散凸最適化ソルバとデモンストレーションソフトウェア
- 多項式行列における離散ルジャンドル双対性(理論)
- アドホックネットワークにおける貪欲幾何ルーティングアルゴリズムに対する統一的な手法
- 同時ブロック対角化を巡る応用数理