包除原理による和集合のサイズの評価について
スポンサーリンク
概要
- 論文の詳細を見る
LinialとNisanは誤差を許容した場合,包除原理を用いてn個の有限集合の和集合のサイズの近似値をk以下の個数の集合の共通部分のサイズだけから求める方法を提案した.この方法を適用することにより,単純に包除原理を適用する場合と比較して,計算時間の大幅な減少が期待できる.彼らは近似の正確さを示す指標として,F(k,n)=sup(|∪^^n__<i=1>A_i|/|∪^^n__<i=1>B_i|)を用いた.但し,上限をとるためにA_1,…,A_n,B_1,…,B_nの変化する範囲は,1≦|I|≦kを満足する任意のI⊆{1,…,n}に対して|∩__<j∈I>A_j|=|∩__<j∈I>B_j|を満足するもの全体とする.彼らは,チェビシェフ多項式を使って定数値関数を近似するという手法によるF(k,n)を評価した.本論文では,ラグランジュ(Lagrange)の補間多項式を用いる手法により,これまで正確な値が求められていなかったF(n-2,n)=1+1/(1/2(「n/2^^n」)-1)を求め,更に,F(n-1,n)=|∪^^n__<i=1>A_i|/|∪^^n__<i=1>B_i|およびF(k,n)の定義の条件を満足する有限集合A_1,…,A_n,B_1,…B_nの具体例を与える.
- 社団法人電子情報通信学会の論文
- 1994-08-25
著者
関連論文
- 双符号形式による楕円曲線暗号系(計算理論とアルゴリズムの新展開)
- n次元立方体の線形配置のコストについて
- n次元立方体の線形配置のコストについて(並列・分散)
- 単調並べ換え関数について(アルゴリズムと計算量理論)
- 和集合のサイズの近似評価について
- アルゴリズムの非確率化と制限付き独立性
- 和集合のサイズの近似評価について
- 包除原理による和集合のサイズの評価について
- $\epsilon$-偏りの確率変数と$\epsilon$-依存の確率変数の間の関係について(計算機構とアルゴリズム)
- 包除原理による和集合のサイズの評価について(理論計算機科学とその周辺)
- Selection Networks with $8n$ log$_2$ $n$ Size and $O$(log $n$) Depth
- 拡張グラフを構成しない線形変換の族について
- 二部グラフの拡張性の評価について(計算機科学の基礎理論)
- 循環型シフト回路の埋め込み面積について (形式言語理論とオートマトン理論)
- 1次元-2状態-スコープ3テセレイションオートマトンの完全性について (情報科学の数学的理論)
- n次元立方体の線形配置のコストについて
- On the Shapes of Vertex Subsets of Hypercubes That Minimize Their Boundary (Algebraic Systems, Formal Languages and Computations)
- 交互三部符号及び交互三部符号形式によるRSA暗号系
- 三部符号及び三部符号形式による RSA 暗号系(計算機科学の理論とその応用)
- The NP-completeness of EULERIAN RECURRENT LENGTH (Algebra, Languages and Computation)
- オイラー小道の最短閉路長の最大値決定問題のNP完全性
- D-1-4 完全グラフのオイラー回帰長の上界について(D-1. コンピュテーション)
- 閉路状多部グラフのオイラー回帰長について
- 完全グラフと完全二部グラフの回帰長について
- 多次元トーラスグラフの線形配置
- On Linear Arrangement Problems on Multidimensional Torus Graphs (Algebraic Semigroups, Formal Languages and Computation)
- オイラー小道上の同一点間の間隔について (言語,代数系および計算機システム)
- ハイパーキューブの二分割コストについて
- 多値論理素子が細分的であるための条件 (情報科学の数学的理論)
- 擬似ランダム関数から擬似ランダム置換への変換について
- オイラー回帰長の上界についての予想