k-setカバーの定義

I’m trying to understand the sparsification lemma by
Impagliazzo, Paturi and Zane (IPZ) (from this article) and in their proof they
reduce the k-SAT problem to the k-set cover problem. But their
definition of the problem seems to be different from the definition
found in other articles where the problem is simply the normal set
cover with the addition that each set is limited to contain a
maximum of k elements from the universe, as can be seen in eg. this
description from Führer and Yu (taken from this article):

Furer,Yu

この問題の解決策は、ユニオンが宇宙をカバーする一連の集合で構成されます。しかし、IPZはこのように問題を述べています。

Impagliazzo, Paturi, Zane

その解決策は、$ mathscr {S} $の S の各集合から少なくとも1つの要素を含む集合
C として定義されます。セットのコレクションは必然的に宇宙をカバーしているとは言えません。サイズの
C を見つける| $ mathscr {S} $ |最小の C
を見つけることは、可能な限り最良の方法で$ mathscr {S}
$から異なるセットに重なる要素を見つけることに対応します。

この長い紹介の後で私の質問はこれです:私はどういうわけかIPZによって与えられた定義を正しく読んでいないのですか?同じ問題を述べる他の方法ですか?あるいは残念ながら同じタイトルが与えられたこの2つの異なる問題はありますか?

ベストアンサー

2番目の定義では、ヒットセットの定式化を使用します。これは、セットカバレッジの問題と同じです。これを見るには、セットと要素の役割を逆にすることができます。詳細については、ウィキペディアページを参照してください。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です