ON GROTSCHEL-LOVASZ-SCHRIJVER'S RELAXATION OF STABLE SET POLYTOPES
スポンサーリンク
概要
- 論文の詳細を見る
Grotschel, Lovasz and Schrijver introduced a convex set containing the stable set polytope of a graph. They proved that the set is a polytope if and only if the corresponding graph is perfect. In this paper, we give an alternative proof of the fact based on a new representation of the convex set described by infinitely many convex quadratic inequalities.
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
-
田村 明久
慶應義塾大学
-
藤江 哲也
兵庫県立大学経営学部
-
Fujie Tetsuya
Kobe University of Commerce
-
Tamura Akihisa
Kyoto University
関連論文
- 1-F-10 Existence of sports schedules with multiple venues
- 汎用並列分枝限定法ツールPUBBを用いた最大クリーク問題の厳密解法(整数計画(1))
- 高次元空間における安定集合多面体(整数計画(1))
- パーフェクト双向グラフ(グラフ・ネットワーク(3))
- On the Local Face Structure of 0-1 Polytopes Related to a Class of Combinatorial Optimizaiton Problems
- Adjacency of the Best and Second Best Valued Solutions in Combinatorial Optimization Problems
- Algorithms for Finding a Kth Best Valued Assignment
- 混合整数計画ソルバーの並列化(パラレルコンピューティングの応用)
- 2次割当て問題への適用におけるIntegral Basis Methodの改良の提案
- 2-F-10 Integral Basis Methodにおける変数選択規則と緩和問題(数理計画(2))
- 2次割当問題への適用によるIntegral Basis Methodの改良の提案(セッション3)
- 総所要時間最小制約二機械フローショップ問題に対する分枝限定法の改善
- 総完了時刻最小化二機械フローショップ問題に対する優越条件(組合せ最適化)
- 2次錐計画法によるディジタルフィルタの設計法
- A Recursive Algorithm for a Class of Convex Min-Max Problems
- 2次割当問題に対するIntegral Basis Method(離散最適化)
- CPLEX MIP OptimizerのPUBB2フレームワークによる並列化について(整数計画(2))
- 混合整数計画問題の解法における前処理の効果検証(整数計画(2))
- ON GROTSCHEL-LOVASZ-SCHRIJVER'S RELAXATION OF STABLE SET POLYTOPES
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- A LINEAR TIME ALGORITHM FOR THE GENERALIZED STABLE SET PROBLEM ON TRIANGULATED BIDIRECTED GRAPHS
- 確率モデルにおける最適化研究部会終了報告(ペーパーフェア)
- 制限付き安定部屋割問題とミニマックス安定部屋割問題(組合せ・グラフ・ネットワーク)
- The Rooted Tree Embedding Problem
- A property of the divorce digraph for a stable marriage
- PUBBによるPCクラスタ環境における並列分枝限定法 (新しいパラダイムとしてのアルゴリズム工学)
- PCクラスタ環境における並列分枝限定法(数理計画(2))
- 汎用並列分枝限定法ツールPUBBによる組合せ最適化問題の厳密解法 (特集「計算と最適化」)
- マッチングモデルと離散凸解析を用いたその拡張 : アルゴリズムの観点から(セッション2)
- マッチングモデル(モデリング-最適化モデリング-)
- ON A DOMINANCE TEST FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH RELEASE DATES TO MINIMIZE TOTAL FLOW TIME
- 第22回FMESシンポジウム「デジタル・エンジニアリングと経営工学」(情報の窓)
- A NEW CHARACTERIZATION OF M^〓-CONVEX SET FUNCTIONS BY SUBSTITUTABILITY
- 安定結婚からサプライチェーンネットワークの安定性へ(離散凸解析)
- 2-B-4 サプライチェーンネットワークの安定性(離散最適化(5))