抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
本論文では,半定値プログラミング,行列ランク,グラフ彩色間の相互作用を考察した。Karger,Motwani,およびスーダンサイト{KMS98}は,グラフの彩色が低ランクの半値行列として符号化できるベクトルプログラムを与える。最適二重解が十分に高いランクを持つならば,半定値プログラミングの補足的緩み条件によって,任意の最適プリミナル解法は,低いランクを持った。著者らは,対応する二重最適解が十分に高いランクを有することを示せるグラフを特徴づけることを試みた。元のKarger,Motwani,およびスダンベクトルプログラムの場合,kツリーである任意のグラフは,十分に高い二重ランクを持ち,対応する低ランクプライム解から彩色を抽出することができることを示す。また,グラフが一意的に着色できないならば,十分に高いランク二重最適解が存在しないことを示した。これにより,二重最適解が十分に高い二重ランクを持つ平面グラフを完全に特性化できる。次に,半定値プログラムをコストで目的関数を持つように修正し,最適二重解が十分に高いランクを持つコスト関数を生成することができるときに探索した。グラフ彩色を与えるこのようなコスト関数を構築することが可能であることを示した。コスト関数の構築はグラフ彩色に対する発見的方法をもたらし,平面グラフの場合においてうまく機能することを示した。本研究は,Colin de Verdi Graphereグラフ不変のサイト{CDV90}(およびColin de Verdi εereの対応する予測)によって動機づけられ,そこでは,二重の実現可能なマトリックスにいくつかの類似性を持つ行列は,グラフが特定のタイプである場合において高いランクを持つ必要がある。二重解の予想とランクの間の関係を調べた。【JST・京大機械翻訳】
