点容量付き内向木詰込問題の計算複雑度

スポンサーリンク

概要

• 論文の詳細を見る

• 本研究では,有向グラフ,根,点容量関数,枝消費関数が与えられたとき,根付き全域内向木をいくつ詰め込めるかという問題を扱う.枝消費関数によって根付き全域内向木の各点における消費が決まる.制約は,各点において,根付き内向木の消費の合計が点容量を超えないことである.この問題を点容量付き内向木詰込問題とよぶことにする.この問題は,センサーネットワークの研究における最も重要な問題である,ネットワークライフタイム問題の1つである.本研究では,グラフが非巡回的な場合,消費関数が距離に依存する場合,などにおける点容量付き内向木詰込問題の計算複雑度を明らかにした.

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

著者

• 宮本 裕一郎

  上智大学

• 今堀 慎治

  東京大学大学院情報理工学系研究科

• 佐々木 美裕

  南山大学

• 柳浦 睦憲

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

• 橋本 英樹

  京都大学情報学研究科

• 今堀 慎治

  東京大学

• 柳浦 睦憲

  名古屋大学

• 橋本 英樹

  名古屋大学

• Yagiura Mutsunori

  Department Of Applied Mathematics And Physics Graduate School Of Informatics Kyoto University

• 今堀 慎治

  名古屋大学工学研究科

関連論文

• 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
• 2-C-6 ミニマックス型の階層型施設配置問題(施設配置)
• 2-F-14 大規模最短路問題に対するダイクストラ法の高速化(グラフ(2))
• ハイブリッドメタ戦略(OR事典Wiki)
• 2-F-3 New Formulation for Scheduling Problem in Multi-Hop Wireless Sensor Networks
• 局所探索法とその拡張 : タブー探索法を中心として
• 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))
• MAX-2-SATに対する分枝限定法
• 矩形パッキング問題に対する厳密解法
• MAX-2-SATに対する分枝限定法(組合せ最適化(4))
• 最短路高速検索のための階層メッシュ疎化法
• 2-E-5 最短路高速検索のための階層メッシュ疎化法(組合せ最適化と応用(3))
• じゃばら折りの複雑さに関する研究
• 時間枠つき配送計画問題に対するパス再結合と適応的パラメータ調整
• 第18回RAMPシンポジウムルポ(情報の窓)
• 2302 生産管理システムの効率的導入のための仮想生産工場 : MRPシステムの導入(OS2-3 生産管理・プロセス最適化)
• 1106 自律型FMSスケジューリング法に関する研究(OS1-1 生産スケジューリング)
• リアルタイムシステムの固定優先度スケジューリングに対する優先度周期探索法
• 1204 格子状経路を持つAGVシステムにおけるオークション方式運用法(OS1-2 生産システムの運用)
• Perfectness and Multicoloring of Unit Disk Graphs on Triangular Lattice Points (Theoretical Computer Science and its Applications)
• 三角格子点上の単位円グラフに対する多重彩色
• 三角格子点上の単位円グラフに対する多重彩色
• Multicoloring Unit Disk Graphs on Triangular Lattice Points
• 対角線付き格子グラフに対するマルチカラーリングの線形時間近似解法
• Weighted Lattice Graph with Diagonals に対するマルチカラーリングの線形時間近似解法(グラフ・ネットワーク)
• MAX-2-SATに対する分枝限定法
• ルール生成に必要なデータ量に関するランダム性に基づいた解析
• 1-D-1 ルール生成に必要なデータ量に関するランダム性に基づいた解析(マーケティング(1))
• 6B2 AN ITERATED LOCAL SEARCH ALGORITHM FOR THE MULTI-RESOURCE GENERALIZED ASSIGNMENT PROBLEM WITH FLEXIBLE ASSIGNMENT COST(Technical session 6B: General model for scheduling and assignment problem)
• 5B1 A GUIDED LOCAL SEARCH ALGORITHM BASED ON A FAST NEIGHBORHOOD SEARCH FOR THE IRREGULAR STRIP PACKING PROBLEM(Technical session 5B: Packing problem)
• オプションプライシングと凸計画問題の関係について(金融工学(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))
• シュタッケルベルグ型ハブ配置モデル
• 3101 小物FMSの自律的運用法の基礎的研究(OS3-1 生産管理)
• 2-F-15 点容量付き内向木詰込問題の計算量(グラフ(2))
• 点容量付き内向木詰込問題の計算複雑度
• 長方形配置問題に対するbest-fit法の効率的な実現
• 切出し・詰込み問題とその応用 : (3)多角形詰込み問題(OR研究の最前線)
• 切出し・詰込み問題とその応用 : (2)長方形詰込み問題(OR研究の最前線)
• 切出し・詰込み問題とその応用 : (1)1次元資材切出し問題(OR研究の最前線)
• 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化 (最適化の数理とアルゴリズム)
• 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化
• 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化(組合せ最適化(2))
• 配置コストをもつ長方形詰込み問題に対する局所探索法について(統合オペレーション(4))
• TD-1-6 組合せ最適化問題に対する局所探索アルゴリズムの開発について
• 配置コストをもつ二次元配置問題に対する局所探索について(組合せ最適化)
• カッティングストック問題に対する線形計画法に基づく局所探索法の提案 (最適化の数理とアルゴリズム)
• 1-A-8 最短路検索の高速化と応用(計算と最適化(1))
• 第14回RAMPシンポジウムルポ(情報の窓)
• 組込みシステムにおけるスケジューリングテーブル作成法 (最適化モデルとアルゴリズムの新展開)
• 排他制約付きナップサック問題における上界の計算法およびその有効性 (最適化モデルとアルゴリズムの新展開)
• 3次元パッキングに対する効率的なbottom-left法 (最適化モデルとアルゴリズムの新展開)
• Bottom-Left 安定点の効率的な列挙法とその応用 (最適化モデルとアルゴリズムの新展開)
• RA-006 3次元箱詰め問題に対する構築型解法の効率的実現法(A分野:モデル・アルゴリズム・プログラミング,査読付き論文)
• 2-C-3 センサネットワークにおけるデータ送受信スケジューリング問題(インフラストラクチャ)
• 2-A-3 クラスタツリーを用いたセンサネットワークの構成方法(都市・地域・国土(1))
• 1-A-12 センサネットワークにおけるクラスタリング手法の改良(都市・地域(3))
• A Quantitative Approach to the Design of the Center Console of Automobiles
• 2-E-19 日本OR学会研究発表会プログラムの自動作成(スケジューリング)
• 2-D-4 研究発表会プログラムの自動作成 : OR学会研究発表会を例として(整数計画)
• 2-A-7 都市のOR研究会(都市・地域・国土(2))
• ゲートウェイ空港配置モデル
• 2-A-5 ゲートウェイ空港の最適配置モデル(輸送・交通(1))
• 近傍ハッシュ法によるエラー許容頻出パターン列挙(一般セッション3)
• 多点対カット問題に対する集合被覆アプローチに基づく近似解法
• LA-004 Analysis of an Edge Coloring Algorithm Using Chernoff Bounds
• 主双対近似解法(新・ORの図解,学会創立50周年記念号)
• 平成12年度春季研究発表会ルポ
• 1-D-6 階層型施設配置問題の定式化について(都市・地域(2))
• 航空路のハブ・スポークシステムについて(組み合わせ最適化(2))
• RA-004 An LP-Based Heuristic Algorithm for the Node Capacitated In-tree Packing Problem
• 頂点容量制約付き有向全域木パッキング問題に対する近似解法
• 平成22年秋季研究発表会ルポ(情報の窓)
• 階層構造を持つミニサム型施設配置問題の厳密解
• 平成22年秋季研究発表会ルポ
• On a Location Problem of Relay Points in a Logistics System
• 2-A-3 一人で歩く距離に着目したMin-Sum型とMin-Max型のネットワークフローモデルと安全下校問題への応用(特別セッション 震災復興・日本再生-都市のOR研究による道筋-(3))
• 1-I-5 電圧降下制約を考慮した停電量最小化問題と輪番停電(離散最適化(1))
• 1-I-3 大学授業時間割の自動編成システムについて(スケジューリング)
• 1-C-2 交差点干渉を考慮した道路ネットワーク設計による渋滞改善(輸送・交通(1))
• 2-B-1 時間割自動編成システムの試作(スケジューリング(1))
• 大学時間割編成モデルの研究
• 1-C-4 リスク最小化に着目したネットワークフローモデルと安全下校問題への展開(都市のOR(1))
• 2-D-9 大学授業時間割の自動編成システムの改良(スケジューリング(3))
• 1-D-7 モジュラリティの上界値算出(離散最適化(2))
• 1-C-5 SimRankを用いた協調フィルタリング(最適化・アルゴリズム(2))
• 2-C-3 不動点定理によるドロネー性の確認(離散最適化(2))
• 2-B-8 呼損率を考慮した容量再配分による医療の地域格差の改善(特別セッション 都市とOR(4))
• 2-E-8 メガキャリアとの競合を考慮したLCCの航空路線編成モデル(輸送・交通(2))
• 1-D-4 大学の定期試験時間割作成問題(スケジューリング)
• 病院アクセシビリティを用いた疾病別需給バランスの視覚化(データから読み解く医療サービス)
• 2-C-1 連結制約と被覆制約を持つ施設配置問題とその解法(輸送・交通(3))

もっと見る 閉じる

スポンサーリンク