ナップサック問題に対する定数時間近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本稿ではナップサック問題に対する定数時間近似アルゴリズム,すなわち出力と最適解の絶対誤差がε以下となる確率が2/3以上である乱択アルゴリズムを示す.ただし,ここではアイテムの総価値は1に正規化されている.各アイテムをサンプリングする確率が各々の価値に比例する重み付きサンプリングを用いることで,ナップサック問題に対して計算時間がO(ε^<-4>logε^<-1>)である定数時間近似アルゴリズムを与える.更に部分和問題に対しては計算時間がO(ε^<-2>)である定数時間近似アルゴリズムを与える.更に,各アイテムが等確率でサンプリングされる一様サンプリングを用いた場合はΩ(n)回のサンプリングが必要であることも示した.
- 2011-03-02
著者
-
伊藤 大雄
京都大学大学院情報学研究科通信情報システム専攻
-
伊藤 大雄
京都大学大学院情報学研究科
-
伊藤 大雄
Ntt通信網研究所
-
伊藤 大雄
豊橋技術科学大学
-
吉田 悠一
京都大学大学院情報学研究科
-
伊藤 大雄
京都大学情報学研究科通信情報システム専攻
-
Ito H
Kyoto University
-
Ito Hiro
School Of Informatics Kyoto University
-
Ito Hiro
京大
-
Ito Hiro
Kyoto Univ. Kyoto‐shi Jpn
-
Ito H
Tokyo Inst. Of Technol. Yokohama‐shi Jpn
-
Ito Hiro
The Graduate School Of Informatics Kyoto University
-
ITO Hiro
Toyohashi University of Technology
-
吉田 悠一
京都大学情報学研究科
-
清島 奨
京都大学情報学研究科
-
伊藤 大雄
京都大学情報学研究科
関連論文
- ハラリイの一般化三並べ(新世代の計算限界-その解明と打破-招待解説論文)
- 無向グラフのk点連結性の検査
- H-彩色可能なグラフのクラスの階層構造のCirculant graphsによる細分化
- マルチホップ無線ネットワークにおける優先領域に基づく中継制御法(無線アドホックネットワーク技術論文特集)
- STOC2009参加報告
- DS-1-1 最大独立集合と最大マッチングに対する定数時間近似アルゴリズムの改善(DS-1. COMP学生シンポジウム,シンポジウムセッション)
- DS-1-14 飛び道具を考慮した逆算法に基づく詰将棋列挙技術(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- スネーキーの置き石一つの必勝法
- 有向グラフにおけるk枝連結性の検査
- 部の大きさの比が高々定数倍の孤立2部クリークの列挙
- 目標枝連結度3の最大被覆供給点配置問題(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 毒まみれ半順序付き集合ゲームの必勝法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 遺伝的な距離に基づいた家系図推定問題
- 孤立した部分グラフの列挙
- DNA配列のプローブ順序固定に必要な最小フラグメント集合
- 最短路ルーティングにおけるバックアップテーブルに関する考察
- LA-3 DNA配列におけるプローブの順序付けに必要な最小フラグメント集合(A. アルゴリズム・基礎)
- インターネットにおける経路ループの回避手法
- グラフの平面描画に関する3つの同値な尺度
- 端末のパケット中継機能を用いた安否確認ネットワークの検討(無線アドホックネットワーク技術論文特集)
- 加群上の畳込み符号による可変レートMPSK符号化変調方式
- 優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討
- B-5-205 マルチホップ無線ネットワークにおける優先領域に基づくルーチングプロトコルの検討
- B-5-204 通信可能時間を考慮したアドホックルーチングプロトコルの特性評価
- レイリーフェージング通信路に有効な環上の畳込み符号
- circulant制約を持った隣接色制約付き彩色問題の応用と解析 (計算理論とアルゴリズムの新展開)
- 位相情報を利用したDS-CDMA用干渉除去受信機特性
- B-5-149 ルーチングゾーンを用いた車々間通信プロトコル
- B-5-140 アドホックネットワークにおけるリンク間コストを考慮したルーチングプロトコル
- B-5-66 フェージング環境下における簡易受信方式の性能評価
- B-5-63 送信タイミング制御を用いたメディア統合予約型CDMAパケット通信方式
- B-5-7 フェージング環境における簡易干渉除去方式の性能評価
- B-5-6 フェージング通信路における位相情報を利用したDS-CDMA用干渉除去受信機特性
- SB-11-3 DS-CDMAシステムにおける簡易適応干渉除去方式
- B-5-169 メディア統合無線ネットワークにおける予約符号を用いたアクセス制御方式
- B-5-168 マルチホップ無線ネットワークにおける優先領域に基づくパケット中継制御法
- B-5-107 スペクトル拡散通信用簡易受信方式 : 簡易PN同期回路の並列接続による性能改善
- B-5-78 レイリーフェージング環境における位相情報を利用したDS-CDMA用干渉除去受信機特性
- 次数制限付最短路木に関する諸問題(グラフ・ネットワーク(2))
- 安否確認ネットワークにおける送信制御のパラメータの影響
- 音声・データ統合予約型パケット無線アクセス方式の検討
- 位相情報を利用したスペクトル拡散通信用干渉除去方式
- DS-CDMAシステムにおける適応干渉除去方式
- メディア統合予約型パケット無線アクセス方式におけるチャネル割り当て方式
- DS-CDMAにおけるMMSE法を用いた干渉除去方式
- サウンダー信号を持つBPSK変調方式の定包絡線化と特性解析
- k-NA枝連結かつ2-NA点連結な最小領域配置問題(グラフ・ネットワーク(1))
- 一般化詰め将棋問題の計算複雑さ : 小駒図式、成駒無し、還元玉、都詰の考慮
- B-5-122 スペクトル拡散通信用簡易受信方式
- B-5-110 スペクトル拡散通信用簡易干渉除去受信方式
- B-5-109 DS-CDMAシステムにおける干渉除去方式
- B-5-108 DS-CDMA システムにおける非直線特性を利用した干渉除去方式
- B-5-26 サウンダー信号を持つBPSK変調方式の定包絡線化
- B-5-4 隣接位置情報を用いた安否確認ネットワークの構築
- 有向グラフ上の高枝連結節点部分集合生成アルゴリズム
- 次数制限のある最短路木作成アルゴリズム
- 舞台照明問題のNP完全性(計算幾何学・図解法)
- 正補混合表現によるグラフ探索時間の削減
- 遠近問題を考慮した送信許可確率可変スロットアロハ方式の検討
- 節点と節点部分集合間の2および3点連結化問題
- BPSC波の定包絡線化について
- 最小枝付加節点領域枝連結度増加問題 : 1-NA枝連結化と2-NA枝連結化問題
- 節点・領域間の枝連結性と距離を保存する疎な全域部分グラフ(グラフ理論(2))
- 荷物の大きさを限定した場合の再配置問題のNP完全性(ネットワーク(1))
- ノード集中を除去する地図変形表示法(ORの実施)
- 見やすく操作性の高いLP地図変形表示法
- 毒まみれ半順序付き集合ゲームの必勝法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 毒まみれ半順序付き集合ゲームの必勝法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- Repairing Flaws in a Picture Based on a Geometric Representation of a Digital Image
- 平面グラフの^^^~-彩色問題
- 優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討
- 優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討
- Efficient Methods for Determining DNA Probe Orders(Discrete Mathematics and Its Applications)
- 目標枝連結度3の最大被覆供給点配置問題(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 目標枝連結度3の最大被覆供給点配置問題(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 情報ネットワークとグラフアルゴリズム : 連結度と領域グラフ
- 位相情報を利用したDS-CDMA用干渉除去受信機特性
- 位相情報を利用したDS-CDMA用干渉除去受信機特性
- 位相情報を利用したDS-CDMA用干渉除去受信機特性
- 手数制限付き一般化詰め将棋のPSPACE完全性について(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 各節点の需要が異なる最小流入点集合配置問題
- メディア統合予約型パケット無線アクセス方式におけるチャネル割り当て方式
- メディア統合予約型パケット無線アクセス方式におけるチャネル割り当て方式
- メディア統合予約型パケット無線アクセス方式におけるチャネル割り当て方式
- メディア統合予約型パケット無線アクセス方式におけるチャネル割り当て方式
- 二次元ハムサンドイッチ定理の一般化とその周辺 (新しいパラダイムとしてのアルゴリズム工学)
- Query-Number Preserving Reductions and Linear Lower Bounds for Testing
- Inferring pedigree graphs from genetic distances
- Variable Rate MPSK Coded Modulation Using Convolutional Codes over Modules
- Channel Assignment Scheme for Integrated Voice and Data Traffic in Reservation-Type Packet Radio Networks (Special Issue on Internet Technology II)
- A Generalization of 2-Dimension Ham Sandwich Theorem (Special Section on Discrete Mathematics and Its Applications)
- A Faster and Flexible Algorithm for a Location Problem on Undirected Flow Networks(Special Section on Discrete Mathematics and Its Applications)
- NP-Hardness of Rotation Type Cell-Mazes (Special Section of Selected Papers from the 12th Workshop on Circuit and Systems in Karuizawa)
- グラフの変形操作における単純性の保存
- Special Section on Discrete Mathematics and Its Applications
- Maximum-Cover Source-Location Problems(Discrete Mathematics and Its Applications)
- 等間隔の折り目を持つ紙の折り畳みの計算量について
- An online algorithm optimally self-tuning to congestion for power management problems (コンピュテーション)
- ナップサック問題に対する定数時間近似アルゴリズム
- グラフの平面凸描画の校長と線形カットサイズと交差操作の関係