半定値計画法にもとづく彩色問題の発見的解法

スポンサーリンク

概要

• 論文の詳細を見る

• 本論文では頂点彩色問題に対する新しい発見的アルゴリズムを提案する.このアルゴリズムでは,各頂点に平面上の単位ベクトルを割当ることにより頂点彩色問題をベクトル配置問題に還元する.このベクトル配置問題は半定値計画問題でああるが,求める半正定値行列のランクに制約があるため,NP-困難である.このため発見的手法により可能解を見付ける.得られたベクトル配置からは簡単に実行可能な彩色が得られる.計算機実験により,密なグラフにおいては提案するアルゴリズムがタブー探索やDSATURよりも色数の少ない彩色を見付けることがわかった.

• 一般社団法人情報処理学会の論文
• 2006-09-27

著者

• 平田 富夫

  名古屋大学大学院情報科学研究科

• 小野 孝男

  名古屋大学大学院情報科学研究科

• 岩城 正哉

  名大

• 柳浦 睦憲

  名古屋大学

• 小野 孝男

  名大

• 柳浦 睦憲

  名大

• 平田 富夫

  名大

• 柳浦 睦憲

  名古屋大学情報科学研究科計算機数理科学専攻

• 柳浦 睦憲

  Department Of Computer Science And Mathematical Informatics Graduate School Of Information Science Nagoya University

• 平田 富夫

  名古屋大学

関連論文

• 局所探索法とその拡張 : タブー探索法を中心として
• A Set Covering Approach for the Pickup and Delivery Problem with Additional Constraints (Numerical Optimization methods, theory and applications)
• 多制約配送計画問題に対する集合被覆アプローチ
• 分枝限定法 : さらなる計算効率の希求(堅く柔らかく…数理計画アプローチ再訪)
• 2-A-3 MAX-2-SATに対する分枝限定法の改良(離散最適化(3))
• 1-A-5 矩形パッキング問題に対する厳密解法(離散最適化(2))
• 時間枠つき配送計画問題に対するパス再結合と適応的パラメータ調整
• 直接計算による楕円曲線上のスカラ倍計算の効率化(情報セキュリティ基礎)
• モンゴメリのトリックを用いた2^kP倍点の改良計算法
• 楕円曲線上のスカラー倍計算の効率化 : ヤコビアン座標系上での直接計算法の提案 (計算機科学基礎理論の新展開)
• 楕円曲線上のスカラー倍点計算法の改良
• D-1-9 集合基底問題の正規基底を求める発見的アルゴリズム(D-1.コンピュテーション,一般セッション)
• 集合基底問題の正規基底を求めるヒューリスティックアルゴリズム
• リアルタイムシステムの固定優先度スケジューリングに対する優先度周期探索法
• 最適化アルゴリズム : この10年の歩み(最適化 : 広がる応用)
• ルール生成に必要なデータ量に関するランダム性に基づいた解析
• 1-D-1 ルール生成に必要なデータ量に関するランダム性に基づいた解析(マーケティング(1))
• COMP2000-14 ネット割当て問題のヒューリスティック解法に関する研究
• ネット割当て問題に対するヒューリスティックアルゴリズムの評価
• D-1-1 ネット割り当て問題に関する一考察
• 2-F-15 点容量付き内向木詰込問題の計算量(グラフ(2))
• 点容量付き内向木詰込問題の計算複雑度
• 長方形配置問題に対するbest-fit法の効率的な実現
• 組込みシステムにおけるスケジューリングテーブル作成法 (最適化モデルとアルゴリズムの新展開)
• 排他制約付きナップサック問題における上界の計算法およびその有効性 (最適化モデルとアルゴリズムの新展開)
• 3次元パッキングに対する効率的なbottom-left法 (最適化モデルとアルゴリズムの新展開)
• Bottom-Left 安定点の効率的な列挙法とその応用 (最適化モデルとアルゴリズムの新展開)
• RA-006 3次元箱詰め問題に対する構築型解法の効率的実現法(A分野:モデル・アルゴリズム・プログラミング,査読付き論文)
• 近傍ハッシュ法によるエラー許容頻出パターン列挙(一般セッション3)
• Fast Algorithms to Enumerate All Common Intervals of Two Permutations and Their Applications(Optimization Theory in Descrete and Continuous Mathematical Sciences)
• 効率の良いモルフォロジー演算が可能なフィルタ形状について
• 中山間地におけるデマンドバスシステムの開発 : デマンドバスの実際的経路探索法
• 多点対カット問題に対する集合被覆アプローチに基づく近似解法
• Triangle-free graphの独立集合問題に対する貪欲アルゴリズムの解析
• LA-004 Analysis of an Edge Coloring Algorithm Using Chernoff Bounds
• Chernoff Bounds を用いた辺彩色アルゴリズムの解析
• 半定値計画法にもとづく彩色問題の発見的解法
• グラフ論的手法を用いた{2, 3}-EC-SNDPに対する近似アルゴリズム(アルゴリズム, ユビキタス社会構築のためのネットワークに対する理論とその応用論文)
• グラフ論的手法を用いた{2, 3}-EC-SNDPに対する近似アルゴリズムの研究
• 重み付き独立集合問題に対する近似アルゴリズム
• 多重グラフの均等辺彩色問題に対するアルゴリズム
• 多重グラフの均等辺彩色問題に対するアルゴリズム
• シストリックアレイによるユークリッド距離変換アルゴリズムの実現
• k-colorableグラフの点彩色問題の近似アルゴリズムに対する議論
• 4-colorableグラフの点彩色問題に対する近似アルゴリズム
• ユークリッド距離変換アルゴリズムのハードウェア化に関する研究
• DS-1-13 A Path Relinking Approach with an Adaptive Mechanism to Control Parameters for the Vehicle Routing Problem with Time Windows
• RA-005 Enumerating bottom-left stable positions for rectangles with overlap
• ゲノム情報解析におけるスコア関数学習の計算複雑度について
• ドビー織機の綜絖枠数最小化問題に対する集合被覆アプローチ
• 多重グラフにおける均等辺彩色を求める高速アルゴリズム
• ドビー織機における必要綜絖枠枚数の最小化
• LA-005 辺縮約問題の近似困難性(A分野:モデル・アルゴリズム・プログラミング)
• 織方図作成における最適化問題のグラフによる定式化 (数値最適化の理論と実際)
• 局所探索法 : 反復改善に基づく最適化の基本戦略(新・ORの図解,学会創立50周年記念号)
• 離散最適化問題に対するメタヒューリスティクス(ここまで使える数理計画法)
• Combinatorial Optimization : Theory and Algorithms (3rd Edition), B. Korte and J. Vygen 著, 出版社 Springer, 発行 2006年, 全ページ 597頁, 価格 53.45ユーロ, ISBN 3-540-25684-9
• 有効ターム数の確率的解析(不確実性の下での意思決定と数理モデル)
• メタヒューリスティクスの世界
• 組合せ最適化の数理--計算困難問題への挑戦 (特集 数理工学の地平--現代における新展開)
• 「メタ・ヒューリスティクス」を使ってみよう!
• 「メタ・ヒューリスティクス」って何ですか?
• 数理計画ソフト初体験 (ユーザのための数理計画応用)
• 大規模な線形順序付け問題に対する高性能な局所探索アルゴリズム
• RA-004 An LP-Based Heuristic Algorithm for the Node Capacitated In-tree Packing Problem
• 頂点容量制約付き有向全域木パッキング問題に対する近似解法
• 第30回SSORを振り返って
• ネット割当てアルゴリズムの改良
• 摂動法によるMAX SAT近似アルゴリズムの改良
• MAX SATに対するハイブリッド法
• 摂動法によるMAX SAT近似アルゴリズムの改良
• Approximation Algorithms for MAX SAT : Semidefinite Programming and Network Flows Approach
• MAX SATに対するYannakakisのアルゴリズムの精密化
• LA-003 ドビー織機における必要綜純粋枚数の最小化(モデル・アルゴリズム・プログラミング)
• 長目綜絖導入による製織可能な織物組織数の増加
• 長目綜絖を用いた場合の織物組織数の増加
• MAX SATに対する近似アルゴリズム
• MAX 3-SATに対する高性能近似アルゴリズム
• [フェロー受賞記念講演]レベルセット法と距離変換アルゴリズム
• 頂点容量付き有向全域木パッキング問題に対するラグランジュ緩和ヒューリスティック (最適化手法の深化と広がり)
• 複雑な個数制約の付いた多資源一般化割当問題について (最適化手法の深化と広がり)
• たて糸張力均一条件下における綜絖枠数最小化 (コンピュテーション)
• レクトリニア多角形配置問題に対する高速な構築型解法
• 距離遺伝2部グラフ上のハミルトン閉路アルゴリズム (アルゴリズムと計算理論の新展開)
• 線形順序付け問題の解法(ランキングとレイティング)
• Heuristic Algorithms for Rectilinear Block Packing (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集)
• たて糸張力均一条件下における綜絖枠数最小化
• たて糸張力均一条件下における綜絖枠数最小化
• 一般化上界制約付き集合多重被覆問題に対する発見的解法 (最適化手法の理論と応用の繋がり)
• 2-C-1 通過節点と通過経路に制約を持つ最短路問題とその解法(離散最適化(2))
• 2-A-9 一般化上界制約付き集合多重被覆問題に対する発見的解法(特別セッション スモールビジネスOR(1))
• 汎用ソルバーによる研究集会開催日程スケジューリングの自動化(論文・事例研究)
• 2-A-5 最適化アルゴリズムを実装する際の留意点について : 組合せ最適化問題に対するメタヒューリスティクスの場合を中心として(特別セッション 最適化の実装技術)
• RA-005 3次元パッキング問題に対するbest-fit法の効率的実現法(アルゴリズム・コンピュテーション(3),A分野:モデル・アルゴリズム・プログラミング)
• 2-B-9 通過節点と通過経路に制約を持つ最短路問題:解法実装の改良(離散最適化(6))
• 学生実験のスケジューリングシステムの構築(現場とつながるOR)
• メタ戦略-問題解決のための実践的解法
• メタヒューリスティクス事始め : まずは局所探索法から(はじめようメタヒューリスティクス)
• 概説メタ戦略(はじめようメタヒューリスティクス)
• 3次元箱詰め問題に対する構築型解法の効率的実現法(一般)

もっと見る 閉じる

スポンサーリンク