一般化安定集合問題に対する半正定値計画緩和
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, Grotschel-Lavasz-Schrijverによる最大安定集合問題に対する凸集合緩和を, 一般化安定集合問題へと拡張する.この凸集合上で線形目的関数を最大化する問題は多項式時間で解くことができる.これにより、パーフェクト双向グラフに対する一般化安定集合問題は多項式時間で解けることが示される.また, 凸集合が多面体であるための必要十分条件は対応する双向グラフがパーフェクトであることを示す.
- 一般社団法人情報処理学会の論文
- 2000-05-19
著者
関連論文
- 2-G-1 半正定値計画問題に対する単体法の実装報告(連続最適化(1))
- A Cutting Plane Approach to Hub Network Design Problems
- A Branch-and-Bound Algorithm for a Class of Three-machine Flowshop Problems (Essays in Commemoration of the Fortieth Anniversary of Department of Management Science)
- 総滞留時間最小化1機械スケジューリング問題に対する優越テストについて(スケジューリング)
- 小売業におけるサービスタイム開始の判断基準に関する一考察(在庫管理)
- 階層的3機械フローショップ問題(スケジューリング)
- 最大リーフ全域木問題に対する厳密解法(グラフ・ネットワーク(2))
- 整凸集合上の離散不動点定理について (ゲーム理論、数理経済学への離散凸解析の応用)
- CPLEX MIP OptimizerのPUBB2フレームワークによる並列化について(整数計画(2))
- 混合整数計画問題の解法における前処理の効果検証(整数計画(2))
- PUBBによるPCクラスタ環境における並列分枝限定法 (新しいパラダイムとしてのアルゴリズム工学)
- PCクラスタ環境における並列分枝限定法(数理計画(2))
- 整数計画問題に対する分枝カット法とカットの理論(OR研究の最前線)
- 半正定値計画とその応用 : 第3回半正定値計画による緩和(2)
- 半正定値計画とその応用 : 第2回半正定植計画による緩和(1)
- Pairwise Stability in a General Two-Sided Matching Model Based on Discrete Concave Utility Functions
- 離散凸解析の数理経済学への応用 (ゲーム理論、数理経済学への離散凸解析の応用)
- 離散凸解析の応用 : 離散凹効用関数を用いた経済モデル(ゲーム理論と離散数学の出会い)
- Proximity Theorems of Discrete Convex Functions (Mathematics and Algorithms of Optimization)
- Proximity Theorems of Discrete Convex Functions
- 数理経済学と離散最適化の新たな出会い
- 不可分財をもつ経済均衡のM凸劣モジュラ流による定式化 (数理最適化の理論とアルゴリズム)
- M凸関数最小化問題に対する領域スケーリング法
- ISMP2000ルポ : Pulleyblank博士による組合せ最適化TOP 10 LIST
- 一般化安定集合問題に対する半正定値計画緩和
- 第22回FMESシンポジウム「デジタル・エンジニアリングと経営工学」(情報の窓)
- Kazuo Murota 著, Matrices and Matroids for Systems Analysis, Springer-Verlag, 483頁, 2000年, 定価15,870円(189マルク)
- 有限点集合の凸包を求める効率のよいアルゴリズム
- 混合整数計画問題に対する分枝カット法
- 最大リーフ全域木問題の上界値計算について