0
私は読んでいる教科書から以下の問題を解決したいと思いますが、どうすればいいか分かりません。実際に私はそれが正しいかどうかわからないのは、セットの要素の最大頻度が必要であり、セットの最大サイズではなく、私が考えることのできない値であると思うからです。ヒッティングセットアルゴリズムの近似
私たちは、集合A = {a 1 ..... a n}と を持っています。例えば、B 1、B 2、...、B mの部分集合の集合です。 問題は、Hの要素の総重量が最小となるような部分集合H⊆Aを見つけることであり、同じ時刻に にHが含まれます。Hは、Hのすべての部分集合と交差します。つまり、すべてのi = 1、...、mに対してH∩B iは∅ではない。 b = max i | B i |サブセットB 1、B 2、...、B mの最大サイズとする。この問題に対して多項式時間 b近似アルゴリズムを与えます。
'b * m'は、すべてのセットのすべてのメンバシップを反復するのにかかる時間です。たとえば、セット内の要素の頻度を計算するために必要な作業です。それは、質問は私には不明なままであると言いました。 「b近似アルゴリズム」の定義は何ですか？彼らが多項式を言うとき、それらはmまたはbの多項式を意味するのでしょうか？ – btilly