通信ネットワークのサイト改良による距離短縮について : 木ネットワークの場合

スポンサーリンク

概要

• 論文の詳細を見る

• 通信ネットワークにおいて各サイトの性能を向上する(つまり、それに接続するリンクの伝送遅延を減らす)ことによって、ネットワークの最大距離を最小コストで指定値以下に下げる問題を考える。サイトの向上法として連続タイプと離散タイプを定義する。連続タイプでは、向上量を連続変数として扱うが、離散タイプでは一定量である。この問題は、ネットワークが一般のグラフであると、どちらのタイプもNP困難である。そこで、グラフが木である場合について、連続タイプの問題はO(|V|^2)時間で解けることを示す。しかし、離散タイプでは、グラフが線であってもやはりNP困難である。

• 社団法人電子情報通信学会の論文
• 2005-04-11

著者

• 茨木 俊秀

  関西学院大学理工学部

• 茨木 俊秀

  関西学院大学

• 茨木 俊秀

  関西学院大学理工学部情報科学科

• YANG Xiao-guang

  Institute of Systems Science, Academy of Mathematics and Systems Science, Chinese Academy of Science

• Yang Xiao-guang

  Institute Of Systems Science Academy Of Mathematics And Systems Science Chinese Academy Of Sciences

関連論文

• 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))
• MAX-2-SATに対する分枝限定法
• MAX-2-SATに対する分枝限定法(組合せ最適化(4))
• 勤務スケジューリング問題に対する局所探索法(医療・福祉・スケジューリング(2))
• 凸型時間ずれコストをもつ資源制約スケジューリング問題(統合オペレーション)
• TD-1-5 汎用スケジューラー : RCPSPによるアプローチ
• 研究室配属のための一方式の提案とその数理的考察
• 1-F-7 研究室配属問題の数理的考察(2)(組合せ最適化と応用(1))
• 1-C-5 研究室配属問題の数理的考察(離散最適化(1))
• 「問題解決エンジン」への道
• 工学としてのアルゴリズム
• 1-D-6 粒子群最適化の2次割当問題への適用(つくばOR学生発表(8))
• 1-D-5 タブー探索によるBIBDの構成(つくばOR学生発表(8))
• 1-B-4 オフライン・オンライン混合ジョブスケジューリング問題に対するラグランジュ緩和法(スケジューリング(1))
• 2-B-9 電車路線を考慮した営業拠点の配置問題(交通(3))
• 2-E-2 可変形状長方形詰込み問題における局所探索アルゴリズム(組合せ最適化と応用(2))
• 1-F-11 汎用ソルバーによる時間割作成の試み(スケジューリング)
• 1-F-6 ネットワークの通信時間改善問題における近似および厳密アルゴリズム(ネットワーク)
• 1-F-5 移動時間が流量に依存する最大動的流問題(ネットワーク)
• 1-F-2 オンライン・オフライン混合ジョブスケジューリング問題(生産・物流)
• LA-001 A New Approach to Approximate the Collision Probability in an Automated Production Line
• 2-C-7 重量付モジュール詰め込みの最適化(組合せ最適化)
• 2-C-6 衝突確率を考慮したバッファ配置問題に対する近似解法(組合せ最適化)
• 衝突確率を考慮したバッファ配置問題に対する計算機シミュレーションを利用した手法
• 1-E-9 生産ラインにおける衝突確率 : 処理時間がアーラン分布に従う場合(待ち行列)
• 1-C-7 周長および面積を考慮した可変形状長方形詰め込み問題(離散最適化(1))
• 1-C-6 時間割の作成とそのパラメータ解析(離散最適化(1))
• 1-A-4 段ボールの製造工程における順序づけ問題(離散最適化(2))
• MAX-2-SATに対する分枝限定法
• ルール生成に必要なデータ量に関するランダム性に基づいた解析
• 1-D-1 ルール生成に必要なデータ量に関するランダム性に基づいた解析(マーケティング(1))
• オプションプライシングと凸計画問題の関係について(金融工学(3))
• 長方形詰込み問題に対する可変近傍探索法(組合せ最適化(4))
• 移動時間コスト関数を考慮した時間枠つき配送計画問題に対する局所探索法 (数理最適化から見た「凸性の深み,非凸性の魅惑」)
• Local Search Algorithms for the Two-Dimensional Cutting Stock Problem with a Given Number of Different Patterns (Captivation of Convexity : Fascination of Nonconvexity)
• 移動時間コスト関数を考慮した時間枠つき配送計画問題に対する局所探索法(組合せ(1))
• 段取り替え制約付きカッティングストック問題に対する列生成法を用いた局所探索法の提案(組合せ(1))
• 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化 (最適化の数理とアルゴリズム)
• 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化
• 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化(組合せ最適化(2))
• 配置コストをもつ長方形詰込み問題に対する局所探索法について(統合オペレーション(4))
• TD-1-6 組合せ最適化問題に対する局所探索アルゴリズムの開発について
• 藤重, 岩田先生Fulkerson賞受賞のニュース(情報の窓)
• Support Vector Machineにおけるルールの利用(線形計画)
• カッティングストック問題に対する線形計画法に基づく局所探索法の提案 (最適化の数理とアルゴリズム)
• 閾グラフの最小辺ランキング全域木について
• 総論 (特集 アルゴリズムの新展開--理論から工学へ)
• データ分類におけるノイズ量の評価について(数理計画(1))
• データからの知識獲得における常識ルールと例外ルールについて(数理計画(2))
• A polynomial time approximation scheme for the minimum maximal matching problem in planar graphs (New Developments of Theory of Computation and Algorithms)
• 平面グラフにおける最小極大マッチング問題に対する多項式時間近似スキーム
• TD-1-7 Webブラウザで見せるアルゴリズム
• カッティングストック問題に対する線形計画法に基づく局所探索法の提案(組合せ最適化(2))
• 一般化2次割当問題に対する大規模近傍探索法の適用について(数理計画(1))
• メタヒューリスティクスの枠組
• メタ戦略とラグランジュ緩和(「スケジューリング技術の新たな展開特集号」)
• Greedy Splitting : A Unified Approach for Approximating Some Partition Problems (Mathematical Optimization Theory and its Algorithm)
• A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraphs (New Developments of Theory of Computation and Algorithms)
• NP困難性の35年 : 克服への道(応用数理の遊歩道(51),フォーラム)
• NP困難性の35年 : PとNPのはざまで(応用数理の遊歩道(50),フォーラム)
• NP困難性の35年 : 広がる世界(応用数理の遊歩道(49))
• NP困難性の35年 : その誕生(応用数理の遊歩道(48))
• 通信ネットワークのサイト改良による距離短縮について : 木ネットワークの場合
• 通信ネットワークのサイト改良による距離短縮について : 木ネットワークの場合
• 「問題解決エンジン」群とモデリング(モデリング-最適化モデリング-)
• ホーン理論とq-ホーン理論の極小関数従属性の推定について
• データの論理的解析におけるルール集合の生成について(数理計画(1))

もっと見る 閉じる

スポンサーリンク