پوشش مجموعه

مسئله پوشش مجموعه، یک مسئله بهینه سازی است که بسیاری از مسئله های انتخاب منابع را مدل سازی می کند. مسئله تصمیم گیری متناظر آن، مسئله NP کامل پوشش مجموعه را تعمیم می دهد و در نتیجه NP سخت است. الگوریتم تقریبی که برای اداره کردن مسئله پوشش راس ارائه شد، در این جا به کار نمی رود. و در نتیجه باید روش دیگری را به کار گیریم. روش اکتشافی حریصانه ای را با نسبت تقریب لگاریتمی بررسی می کنیم. یعنی هر چه اندازه نمونه بزرگتر می شود، اندازه جواب تقریبی ممکن است نسبت به اندازه جواب بهینه رشد کند. چون، تابع لگاریتمی، خیلی کند رشد می کند، این الگوریتم تقریب ممکن است نتایج مفیدی ارائه ندهد.
معرفی بر الگوریتم ها
معرفی بر الگوریتم ها ترجمه : جعفرنژادقمی
Algorithmic construction of sets for k-restrictions author: Noga Alon
A Threshold of ln n {\displaystyle n}   for Approximating Set Cover author: Uriel Feige
On the hardness of approximating minimization problems author: Carsten Lund
نمونهٔ ( X , F ) {\displaystyle (X,F)}   از مسئلهٔ پوشش مجموعه، شامل مجموعهٔ متناهی X و خانوادهٔ F از زیرمجموعه های X است . به طوری که هر عنصر X متعلق به حداقل یک زیرمجموعه در F است:( اگر S   ∈ F {\displaystyle S\ \in F}   را برابر با p بگیریم)
X   =   ⋃ p S {\displaystyle X\ =\ \bigcup _{p}S}
می گوییم زیرمجموعه S ∈ F {\displaystyle S\in F}  ، عناصرش را می پوشاند. مسئله، یافتن می نیمم اندازهٔ A   ⊆ F {\displaystyle A\ \subseteq F}  است که اعضای آن، تمام X را می پوشاند: (اگر S   ∈ A {\displaystyle S\ \in A}   را برابر با q بگیریم)