כל מה שרצית לדעת על בעיית כיסוי קבוצות:
בעיית כיסוי קבוצות (באנגלית: Set Cover Problem) היא הבעיה האלגוריתמית הבאה: נתונה משפחה סופית S של קבוצות סופיות, שאיחודן הוא הקבוצה U.
יש למצוא תת-משפחה של S בגודל מינימלי, שאיחוד הקבוצות בה הוא U כלומר יש למצוא את הכיסוי הקטן ביותר לקבוצה U שהוא תת-כיסוי של S.
לדוגמה, בהנחה ונתונה לנו קבוצה ומשפחה של קבוצות .
איחוד של כל הקבוצות ב S מכיל את כל האלמנטים ב U, לעומת זאת כיסוי הקבוצות הקטן ביותר עבור מקרה זה יהיה: .
שאלה זו היא NP-קשה; השאלה האם התשובה קטנה מ-k נתון היא NP-שלמה.
הבעיה נכללת ברשימת 21 הבעיות ה-NP-שלמות של ריצ'רד קארפ.
הבעיה הזו היא דוגמה אופיינית וחשובה של בעיית אופטימיזציה דיסקרטית.
תכונה חשובה של בעיה בסיסית זו היא שניתן למצוא באופן יעיל קירוב סביר לאופטימום שלה – ניתן למצוא באופן יעיל פתרון לבעיה הקרוב לאופטימום, בסיבוכיות שתהיה בסדר גודל של הלוגריתם של גודל הקבוצה אותה יש לכסות.
הבעיה הזו חשובה בתחום אלגוריתמי קירוב, ונאמר עליה, על ידי ו.
וזירני, כי היא בעיה ש"לימודה הוביל לפיתוח טכניקות יסודיות לתחום הכולל" של אלגוריתמים מקורבים.
הדרך הפשוטה ביותר לבצע את זה היא על ידי אלגוריתם חמדן.
באלגוריתם זה בונים תת-משפחה של S כדלקמן: מתחילים ממשפחה ריקה ומצרפים לה מדי צעד קבוצה מ-S המגדילה ככל האפשר (בשלב הנוכחי) את מספר האיברים באיחוד הקבוצות שבמשפחה.
לחלופין, ניתן למצוא קירוב טוב לפתרון בהסתמך על תכנון לינארי בשילוב עם תהליך של עיגול מקרי.