M凸劣モジュラ流問題に対する容量スケーリング法

スポンサーリンク

概要

• 論文の詳細を見る

• M凸関数は,整数格子点上で定義された非線形・非分離関数のクラスとして提案された離散凸関数である.フローの境界に対する費用がM凸関数で与えられているM凸劣モジュラ流問題は,最小費用流問題,劣モジュラ流問題の自然な拡張であり,効率良く解くことができる組合せ最適化問題の最も一般的な枠組みの一つである.本稿では,Fleischer-岩田-McCormick(2002)による劣モジュラ流問題に対する容量スケーリング法に基づき,更に,最大劣モジュラ流問題を解くことによるポテンシャルの更新を伴う新しい手続きを導入し,M凸劣モジュラ流問題に対する効率的な容量スケーリング法を提案する.

• 一般社団法人情報処理学会の論文
• 2004-03-19

著者

• 森口 聡子

  産業技術大学院大学

• 室田 一雄

  東京大学:prest:jst

• 室田 一雄

  京都大学

• 室田 一雄

  東京大学大学院 情報理工学系研究科

• 森口 聡子

  東京工業大学情報理工学部

• 森口 聡子

  上智大学

• 岩田 覚

  京都大学

• 岩田 覚

  東京大学大学院工学系研究科計数工学専攻

• 室田 一雄

  Department Of Mathematical Informatics Graduate School Of Information Science And Technology Univers

関連論文

• 平成22年春季研究発表会ルポ(情報の窓)
• 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-D-3 混合行列束のKronecker標準形の組合せ論的解析(離散・組合せ最適化(5))
• 特異値計算アルゴリズム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分解法(離散最適化)
• 離散凸最適化ソルバとデモンストレーションソフトウェアの公開
• 第61回シンポジウムルポ(情報の窓)
• 2-A-13 離散凸解析とその応用(計算と最適化(3))
• 同期型e-Learningシステムを利用したプロジェクト型学習科目の設計と実践(若手の会(5))
• 2302 生産管理システムの効率的導入のための仮想生産工場 : MRPシステムの導入(OS2-3 生産管理・プロセス最適化)
• 最適化アルゴリズムと離散凸構造
• 2-E-7 M^〓/L^〓凸関数最小化における連続緩和の実験的評価(離散最適化)
• 離散凸解析 : 離散最適化に対するボトムアップ的アプローチ(新・ORの図解,学会創立50周年記念号)
• 1106 自律型FMSスケジューリング法に関する研究(OS1-1 生産スケジューリング)
• 2-E-3 混合多項式行列の小行列式の最大次数を計算する組合せ緩和法(離散最適化(1))
• 2-F-10 POS分析とアンケートに基づく大学生協の食育向上の試み(大学でのOR)
• 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凸関数(組合せ最適化(3))
• ネットワークサービスプラットフォームを利用したディジタル旅日記サービスの提案
• ネットワークサービスプラットフォームを利用したディジタル旅日記サービスの提案
• ネットワークサービスプラットフォームを利用したディジタル旅日記サービスの提案
• 1-B-6 線形計画問題の符号可解性(組合せ最適化(1))
• 符号対称行列のSylvester指数(組合せ最適化(6))
• 2-C-9 リンキングシステムによるM凸関数の変換(グラフ・ネットワーク(2))
• 2-D-12 行列*代数のブロック対角化アルゴリズムと半正定値計画問題への応用(非線形計画(2))
• 組合せ最適化と凸解析(文献賞)
• 組合せ論的緩和法 : 組合せ最適化技法による代数計算(組合せ最適化)
• ポリマトロイド対の普遍基の特徴付け
• 1204 格子状経路を持つAGVシステムにおけるオークション方式運用法(OS1-2 生産システムの運用)
• 在庫管理と離散凸関数(OR研究の最前線)
• 第17回RAMPシンポジウムルポ(情報の窓)
• フィードバックのある資源配分問題
• 離散凸解析ってなんですか?(アイ・サイ問答教室)
• L凸関数に対する離散ヘッセ行列(離散最適化)
• M凸劣モジュラ流問題に対する容量スケーリング法
• M凸劣モジュラ流問題に対する容量スケーリングアルゴリズム(最適化(1))
• 電気抵抗回路に基づくグラフ上の半教師付き学習機械(テーマセッション,文字認識・文書理解)
• 劣モジュラ費用集合被覆問題
• 平成22年春季研究発表会ルポ
• 混合行列束のKronecker標準形の組合せ論的解析
• 劣モジュラ流問題に対するコストスケーリング算法(組み合わせ最適化(1))
• Approximate- Weight-Splitting Algorithm for a Minimum Common Base of a Pair of Matroids(Mathematical Structure of Optimization Theory)
• マトロイドの最適共通基問題に対するオークション算法(グラフ・ネットワーク)
• 回転変位を持つ対称構造物のブロック対角化手法〔英文〕
• 回転変位を持つ対称構造物のブロック対角化手法--理論編
• 1-A-9 劣モジュラ最適化(計算と最適化(1))
• 2-C-4 独立偶因子の組合せ的アルゴリズム(離散最適化(3))
• KSMAP「OR若手の会」の紹介
• 一般グラフのDulmage-Mendelsohn型分解(グラフ・ネットワーク(2))
• 選択組立におけるマッチング算法(組合せ最適化(2))
• 1-B-9 グラフの向き付けに関する最適化問題の解法(組合せ最適化(2))
• 多変数多項式行列の構造的弱既約性と構造的可制御性判定への応用
• Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of Subdeterminants
• 多項式行列に対する組合せ論的緩和法の実現について(組合せ最適化)
• 分割行列の階層的分解(II) : 同値変換(離散数学)
• 分割行列の階層的分解(I) : 相似変換(離散数学)
• ネットワークサービスプラットフォームを利用した家庭用セキュリティサービスロボット
• ネットワークサービスプラットフォームを利用した家庭用セキュリティサービスロボット
• "一般性"を仮定した分割行列に関する最大最小定理とDulmage-Mendelsohn型分解(組合せ最適化)
• 独立マッチングの基本構造に関する一定理(組合せ最適化)
• Rigorous Proof of Cubic Convergence for the dqds Algorithm for Singular Values
• 306 離散凸最適化による予備品在庫管理アプリケーションの開発(OS3-2 生産システムの最適化手法)
• 離散凸解析(Discrete Convex Analysis)((離散可積分系と離散解析)
• 離散凸解析 : 組合せ最適化における凸性
• 離散凸解析(最適化の数理)
• マトロイドと凸解析(最適化の数理における離散と連続構造)
• Millerの後退漸化式法再考(数値計算アルゴリズムの現状と展望II)
• F.シャトラン/伊理正夫・伊理由美訳, 行列の固有値, シュプリンガー・フェアラーク東京, 1993, 344 pp.
• 114 製造業における持続的競争優位のための「戦略的PMO」の提案(OS1-3 技術の伝承と展開I)
• 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))
• 離散凸最適化ソルバとデモンストレーションソフトウェア
• 多項式行列における離散ルジャンドル双対性(理論)
• 同時ブロック対角化を巡る応用数理

もっと見る 閉じる

スポンサーリンク