ポリマトロイド対の普遍基の特徴付け
スポンサーリンク
概要
- 論文の詳細を見る
多端子ネットワークN=(V、A、c;S^+、S^-)(ただし、V:頂点集合、A:枝集合、c:枝容量S^+(⊂V):供給(入口)頂点集合、S^-(⊂V):需要(出口)頂点集合)の流れに対して、供給点から流入する流れを(s^+(v)|v∈S^+)、需要点から流出する流れを(s^-(v)|v∈S^-)と書くとき、供給量ベクトルS^+、需要量ベクトルS^-の成分がそれぞれできるだけ平均化されるような最大流を求める問題がN。Megiddo〔6〕によって考察され、さらに藤重〔4〕によって、一つのポリマトロイドの辞書式最適基を求める問題に拡張されている。本論文では、供給頂点S^+と需要頂点S^-の間に何らかの一対一対応が定められているときに、供給量ベクトルS^+と需要量ベクトルS^-ができるだけ近くなるような最大流を求める問題を、同一の台集合をもつ二つのポリマトロイドの基x、yで「できるだけ近い」対(x、y)を求める問題として扱う。「できるだけ近い」ことの意味として(1)Kullback-Leibler情報量の一般化であるf^-発散に関してxとyとの距離が最小であること、および(2)xとyの対応する成分の比が辞書式順序で最大であること、のどちらかの基準を考えても、最適解(x、y)の集合がポリマトロイド対の普遍基の集合と一致することが示される。
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
関連論文
- 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))
- 特異値計算アルゴリズム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の解法
- ロバスト混合整数計画に対するBenders分解法(応用)
- ロバスト混合整数計画に対するBenders分解法(離散最適化)
- 離散凸最適化ソルバとデモンストレーションソフトウェアの公開
- 2-F-10 POS分析とアンケートに基づく大学生協の食育向上の試み(大学でのOR)
- 一般化ポリマトロイド上のM凸関数(組合せ最適化(3))
- 2-C-9 リンキングシステムによるM凸関数の変換(グラフ・ネットワーク(2))
- 2-D-12 行列*代数のブロック対角化アルゴリズムと半正定値計画問題への応用(非線形計画(2))
- 組合せ最適化と凸解析(文献賞)
- 組合せ論的緩和法 : 組合せ最適化技法による代数計算(組合せ最適化)
- ポリマトロイド対の普遍基の特徴付け
- L凸関数に対する離散ヘッセ行列(離散最適化)
- M凸劣モジュラ流問題に対する容量スケーリング法
- M凸劣モジュラ流問題に対する容量スケーリングアルゴリズム(最適化(1))
- 電気抵抗回路に基づくグラフ上の半教師付き学習機械(テーマセッション,文字認識・文書理解)
- Proximity Theorems of Discrete Convex Functions
- Rigorous Proof of Cubic Convergence for the dqds Algorithm for Singular Values
- A note on the dqds algorithm with Rutishauser's shift for singular values
- 2-D-8 離散ヘッセ行列と凸拡張可能性に関する注意(最適化)
- 1-D-9 半正定値離散ヘッセ行列をもつ離散非凸関数の構成(離散最適化(2))
- 離散凸解析から見たDijkstra法
- 1-C-9 離散凸解析を利用したコールセンターのシフトスケジューリング(離散最適化(1))
- 離散凸最適化ソルバとデモンストレーションソフトウェア
- 多項式行列における離散ルジャンドル双対性(理論)
- 1-F-7 整数格子点上の安定結婚問題がもつ束構造(離散最適化(2))
- 同時ブロック対角化を巡る応用数理