最小ブロック転送問題の近似可能性と近似不可能性
スポンサーリンク
概要
- 論文の詳細を見る
本稿では以下の問題を考える:有向非巡回グラフが与えられたとき,グラフ上の根から葉までのすべての道を見て,その外部有向辺数の最大値を最小にするように,それぞれのノードをサイズが高々Bであるブロックに分割することを目標とする.ここで,外部有向辺とは異なるブロックに属すノード間の有向辺とする.本問題は一般的にはNP困難となることを示すことができる.本稿では,B=2の場合には,3/2近似アルゴリズムが存在し,近似の観点から3/2の近似率は最適であることを示す.これまでに知られた近似率は2であった.また,B≧3の場合にも,P≠NPと仮定すると,任意の正数εに対して,3/2-ε近似アルゴリズムが存在しないことを示す.さらに,B=3の場合,入力グラフを階層グラフに限定すると,2近似アルゴリズムが存在することを示す.すなわち,既知の近似率3を改善する.
- 社団法人電子情報通信学会の論文
- 2006-03-15
著者
-
宮野 英次
九州工業大学大学院情報工学研究院
-
朝廣 雄一
九州産業大学情報科学部
-
古川 哲也
九州大学大学院経済学研究院
-
古川 哲也
九州大学大型計算機センター
-
池上 佳一
九州工業大学情報工学部
-
朝廣 雄一
九州産業大学情報科学部情報科学科
-
宮野 英次
九州工業大学
関連論文
- 直径d部分グラフ最大化問題の計算複雑さ
- 論文審査の要旨(矢加部正幸氏学位授与報告)(平成14年度学位論文要旨・論文審査要旨)
- 論文審査の要旨(陳暁栄氏学位授与報告)(平成14年度学位論文要旨・論文審査要旨)
- 最大出次数最小化問題の各種グラフクラスに対する計算複雑さ
- 直径d部分グラフ最大化問題の近似について
- 集合ラベルを持つデータの集約範囲の記述
- 論文審査の要旨(高木昇氏学位授与報告)(平成14年度学位論文要旨・論文審査要旨)
- 完全二分木の直線埋め込みについて
- 最大支配問題
- グラフの最小出次数最大化問題
- 協調能動型データベースシステム技術の研究に向けて (メディア統合および環境統合のための高機能データベースシステム、および一般)
- 最小マンハッタンネットワーク問題の近似について (理論計算機科学の深化と応用)
- 連合データベースシステムにおける導出データの一貫性管理法
- 連合型データベースシステムにおける具現化した導出データの管理法
- 経済学部における全学教育と専攻教育の連節(授業・教育の連節)
- 一貫性と隔離性の細分に基づく並行実行の制御
- 1-E-8 黒字倒産を防ぐための経営計画の分析手法(スケジューリング)
- 一貫性と隔離性の細分による並行実行の正当性の検証
- 隔離性の分割による正当なスケジュールの検討
- 意味集合による複数の意味のデータの記述(データ応用,夏のデータベースワークショップDBWS 2006)
- 意味集合による複数の意味のデータの記述(データ応用)
- 意味集合による複数の意味のデータの記述
- 階層的分類における複数の意味を持つデータの利用(情報融合)
- 最小ブロック転送問題の近似可能性と近似不可能性
- 並行ワークフローにおけるデータの従属性(DE: データ工学理論, データ工学とメディア理解との融合)
- 並行ワークフローにおけるデータの従属性(DE: データ工学理論, データ工学とメディア理解との融合)
- 並行実行のためのワークフローの記述と制御
- Webサービスにおけるトランザクションの隔離性
- 並行実行を考慮したワークフローの記述法
- ワークフロートランザクションの隔離性(データベースと感性,デザイン,バイオインフォマティクス,音楽,環境,医学,建築分野との連携)
- 一貫性判定と処理単位の整構造による独立化可能スケジュール
- トランザクショナルワークフロの一貫性と隔離性
- トランザクショナルワークフロの一貫性と隔離性
- データベースを用いたデータ解析のための集合操作
- 集合の階層を保持するデータベース
- データベースを用いたデータ解析のための集合操作
- 統計解析パッケージとの連携利用を実現するためのデータベース構築法
- オブジェクト指向データベースの会話的設計支援方式
- バンプ探索における解の精度(セッション1)
- バンプ探索における解の精度(セッション1)
- 処理効率向上のためのネットワーク構造の変換(知識ベースとデータベースの統合化に関する研究)
- 守備特訓に喘ぐ外野手のための捕球経路問題 (計算機科学基礎理論の新展開)
- 論文審査の要旨(沙飛氏学位授与報告)(平成14年度学位論文要旨・論文審査要旨)
- サイクルグラフ上での地図作成問題に対する重み付き最近傍アルゴリズム
- 試問予定表作成問題の計算複雑さ
- 移動物体回収問題 : ロボットに効率良く物体を回収させるアルゴリズムの設計のために(学生/教養のページ)
- 移動物体回収問題
- ブックマーク問題の近似について
- 並行処理制御における独立化可能性の有効性検証と特徴分析
- 並行処理制御における独立化可能クラスの有効性検証 : 非施錠方式に対するシミュレーション
- 一貫性情報を利用した能動的な並行処理制御法
- 並行処理制御における独立化可能クラスの有効性検証 : 施錠方式に対するシミュレーション
- 一様メトリックにおけるソーティングバッファ問題のNP困難性
- 顧客データベースにおけるbump huntingとその精度
- バンプ探索における解の精度
- 最大重み付き出次数を最小化するグラフ有向化問題の近似(不)可能性
- Bump hunting 問題における極値統計の応用(日本計算機統計学会 第19回シンポジウム)
- 最大出次数を最小化するグラフ有向化について
- 期限付き移動物体に対する回収アルゴリズム
- マルチバージョンデータベースにおけるワークフローに基づく並行処理制御
- 一貫性情報を用いたマルチバージョン並行処理制御
- ワークフローに基づく協同作業環境
- 操作の整合性を保証する処理単位モデル
- 一貫性判定と処理単位の構造による協調型データベースの並行処理制御
- 資源増加を許したOVSF符号割当問題に対する2競合アルゴリズム
- 頂点数を最大とする正則誘導連結部分グラフ問題の計算複雑さ (コンピュテーンョン)
- リンク構造をもつデ-タベ-スからの非正規関係の効率的生成 (新しいデ-タベ-ス技術論文特集)
- リンク構造を用いた非正規関係の冗長性の削減
- 進化する多重階層索引の実現方式
- 資源増加を許したOVSF符号割当問題に対する(1 + ε)-競合アルゴリズム
- 最大支配問題
- タイル縁に上書きルールを用いた敷き詰め問題
- タイル縁に上書きルールを用いた敷き詰め問題
- 効率の良い罫線描画について
- 従属性を用いた多次元データベースの設計
- 従属性を用いた多次元データベースの設計
- OLAPデータキューブにおける範囲合計配列の更新
- 折線上を移動する物体に対する回収問題の困難性
- 期限付き移動物体に対する回収アルゴリズム
- 移動系における最大個数巡回アルゴリズム (計算機科学基礎理論の新展開)
- 容量を制限した場合の移動物体巡回問題 (計算機科学基礎理論の新展開)
- ネットワ-ク構造における効率の良い更新処理のための条件 (新しいデ-タベ-ス技術論文特集)
- 複合階層索引の質問記述能力
- 複合階層索引の質問記述能力
- 複合階層索引を用いたデータ索引システムの利用者インタフェース
- 頂点数を最大とする正則誘導連結部分グラフ問題の計算複雑さ
- 並行処理制御におけるホーン節で表された一貫性情報の利用
- グラフ判定方式に基づく一貫性情報を用いた並行処理制御の実現法
- 一貫性情報に基づく処理単位の動的再構成
- 並行処理制御方式による独立化可能クラスと直列可能クラスの比較
- メタ戦略アルゴリズムに対するロバストな並列化 (計算機科学基礎理論の新展開)
- 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化
- 操作間の関連を用いた並行実行の分析
- 一貫性情報を用いたデータベースの並行処理制御
- 状態制約に基づく並行処理の非直列可能制御方式
- データの多重分類階層の構成
- 協調作業用データベースの階層ビューインタフェース
- リンク構造データベースにおけるスキーマの独立性
- 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化
- 次数指定した最大正則誘導部分グラフ探索問題(一般)