MIN 3-SET COVERの近似困難性
スポンサーリンク
概要
- 論文の詳細を見る
台集合UとUの部分集合の族Fが与えられたとき,Fからできるだけ少ない数の集合を選び,これらの和集合でUのすべての要素をカバーする問題をMIN SET COVERと呼ぶ.また,部分集合それぞれに含まれる要素数が高々k(≥3)個に制限されている問題はMIN k-SET COVERと呼ばれる.この論文ではMAX 3-SAT(l)からのリダクジョンを用い,MIN 3-SET COVERは任象のδ>0に関して1+⋴_l/12l-δ近似がNP困難であることを示す.ここで,⋴_lはSATからMAX 3-SAT(l)へのギャップ導入パラメータである.
- 一般社団法人情報処理学会の論文
- 2003-11-07
著者
-
平田 富夫
名古屋大学大学院工学研究科
-
大月 英明
Department Of Software Engineering Nanzan University
-
大月 英明
名古屋大学大学院工学研究科電子情報学専攻
関連論文
- 直接計算による楕円曲線上のスカラ倍計算の効率化(情報セキュリティ基礎)
- モンゴメリのトリックを用いた2^kP倍点の改良計算法
- 楕円曲線上のスカラー倍計算の効率化 : ヤコビアン座標系上での直接計算法の提案 (計算機科学基礎理論の新展開)
- 楕円曲線上のスカラー倍点計算法の改良
- D-1-9 集合基底問題の正規基底を求める発見的アルゴリズム(D-1.コンピュテーション,一般セッション)
- 集合基底問題の正規基底を求めるヒューリスティックアルゴリズム
- 詳細配置問題を組み込んだ配線モデル
- 詳細配置問題を組み込んだ配線モデル
- COMP2000-14 ネット割当て問題のヒューリスティック解法に関する研究
- D-1-1 ネット割り当て問題に関する一考察
- ユークリッド距離変換アルゴリズムの効率化
- 効率の良いモルフォロジー演算が可能なフィルタ形状について
- 効率の良いモルフォロジー演算が可能なフィルタ形状について
- 中山間地におけるデマンドバスシステムの開発 : デマンドバスの実際的経路探索法
- 平面配線における配線可能性検証の効率化
- 配線可能性検証のための容量判定グラフとフロー導出グラフ
- 配線可能性検証のための容量判定グラフの提案
- 配線可能性検証のための容量判定グラフの提案
- 多点対カット問題に対する集合被覆アプローチに基づく近似解法
- 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グラフの点彩色問題に対する近似アルゴリズム
- ユークリッド距離変換アルゴリズムのハードウェア化に関する研究
- ドビー織機の綜絖枠数最小化問題に対する集合被覆アプローチ
- ドビー織機における必要綜絖枠枚数の最小化
- 2層配線における発見的ビア数最少化手法
- 2層配線における発見的ビア数最少化手法
- 平面配線可能性検証アルゴリズムの実現 (電子システムの設計技術と設計自動化)
- 配線可能性検証のためのフロー計算アルゴリズム
- 配置処理のための領域分割の改善
- 配置処理のための領域分割の改善
- B-スプライン関数による布の傷の高速検出
- B-スプライン関数による布の傷の高速検出
- Inapproximability of the Minimum Biclique Edge Partition Problem
- Inapproximability of the Edge-Contraction Problem(Discrete Mathematics and Its Applications)
- LA-005 辺縮約問題の近似困難性(A分野:モデル・アルゴリズム・プログラミング)
- MIN 3-SET COVERの近似困難性
- MIN 3-SET COVER の近似困難性
- 織方図作成における最適化問題のグラフによる定式化 (数値最適化の理論と実際)
- ネット割当てアルゴリズムの改良
- 摂動法によるMAX SAT近似アルゴリズムの改良
- MAX SATに対するハイブリッド法
- 摂動法によるMAX SAT近似アルゴリズムの改良
- MAX SATに対するYannakakisのアルゴリズムの精密化
- LA-003 ドビー織機における必要綜純粋枚数の最小化(モデル・アルゴリズム・プログラミング)
- 長目綜絖導入による製織可能な織物組織数の増加
- 長目綜絖を用いた場合の織物組織数の増加
- 近似アルゴリズムの実用化
- デマンドバスシステムにおける実際的経路探索法
- 警備員経路アルゴリズムの時間解析について
- MAX SATに対する近似アルゴリズム
- ユークリッド距離変換アルゴリズム
- 距離遺伝2部グラフ上のハミルトン閉路アルゴリズム (アルゴリズムと計算理論の新展開)
- たて糸張力均一条件下における綜絖枠数最小化