離散凸最適化における共役スケーリング法

スポンサーリンク

概要

• 論文の詳細を見る

• 離散凸関数の共役性を利用した新しいスケーリング技法を導入する.その結果, 離散凸関数を費用関数とする劣モジュラ流問題に対する弱多項式時間算法が得られる.この算法によって, 離散凸解析におけるFenchel型双対定理の両辺の最適解を多項式時間で求めることが可能となる.

• 一般社団法人情報処理学会の論文
• 1998-10-28

著者

• 繁野 麻衣子

  筑波大学大学院システム情報工学研究科社会システム・マネジメント専攻

• 岩田 覚

  大阪大学

• 繁野 麻衣子

  筑波大学

• 繁野 麻衣子

  筑波大学大学院システム情報工学研究科社会システムマネジメント専攻

関連論文

• 1-B-9 従属条件付きマッチング問題に関する一考察(離散最適化(2))
• 顧客志向ビジネス・イノベーションのためのサービス科学に基づく高度専門職業人育成プログラムの開発(サービスイノベーションとAIと教育〔第3回〕)
• 最大密度部分集合問題と近似2分探索による解法
• 実市街地データへの難燃化整備計画問題の適用可能性
• 延焼経路ネットワークを用いた難燃化整備計画問題の近似解法の比較(輸送・交通(2))
• ネットワークの頂点切断集合と用いた難燃化整備計画問題の解法について(都市・交通)
• 劣モジュラ関数最小化の高速スケーリング算法
• 劣モジュラ関数最小化の完全に組合せ的なアルゴリズム
• 離散凸最適化における共役スケーリング法
• 劣モジュラ流問題に対するコストスケーリング算法(組み合わせ最適化(1))
• Approximate- Weight-Splitting Algorithm for a Minimum Common Base of a Pair of Matroids(Mathematical Structure of Optimization Theory)
• マトロイドの最適共通基問題に対するオークション算法(グラフ・ネットワーク)
• ネットワーク上の被覆型施設配置問題(グラフ・ネットワーク(3))
• 設備更改のスケジューリング問題への基本分割の応用(スケジューリング)
• 1-D-4 最大密度部分集合問題と近似2分探索による解法(つくばOR学生発表(8))
• 1-D-1 ブロードキャストアルゴリズムに対するビザンチンフォールトトレラント性の指標(つくばOR学生発表(4))
• New bounds on the minimum calls of failure-tolerant gossiping
• 2.質の高いサービスを提供するためのスタッフスケジューリング(サービスイノベーションへの数理的アプローチ)
• 隣接数に着目したハイパーグラフ上のコミュニティ抽出 (最適化手法の深化と広がり)
• 2-H-5 VCGメカニズムによるオークションの最適供給量に関する一考察(ゲーム理論(2))
• 2-A-5 数理モデルによる地域チェンジ・プロジェクト(特別セッション 震災復興・日本再生-都市のOR研究による道筋-(4))
• 1-D-5 交通サービスにおける最適化手法によるスケジューリング事例(特別セッション サービスサイエンス)
• 省電力化のためのマッチングに基づく仮想計算機パッキングアルゴリズム
• 1-D-3 消費電力削減のための仮想計算機パッキング問題に対する解法(節電)
• 1-E-8 GPS配車管理システムデータによるタクシー顧客利用分析事例(特別セッション サービスサイエンス)
• 1-C-1 グラフ上の離散ボロノイゲームにおけるナッシュ均衡(最適化・アルゴリズム(1))
• 2-A-10 スタッフスケジューリングのフレームモデル構築に向けて(特別セッション スモールビジネスOR(2))
• 2-E-6 タクシー配車計画へのOR手法の適用事例(輸送・交通(1))
• 1-D-5 筑波大学附属病院における病床割当のモデル化(医療スケジューリング)
• 2-E-10 筑波大学附属病院における病床管理システムの作成(スケジュール(2))

もっと見る 閉じる

スポンサーリンク