בעיית כיסוי קבוצות (Set Cover Problem) עוסקת באוסף של תתי־קבוצות S שמאחדות קבוצה אוניברסלית U. כיסוי הוא תת־קבוצה של S שאיחודה הוא כל U. המטרה היא למצוא כיסוי שמשתמש בכמה שפחות קבוצות מ־S. בגרסת ההכרעה שואלים אם קיים כיסוי בגודל לכל היותר k.
בעיית כיסוי הקבוצות היא בעיה מרכזית בקומבינטוריקה, באופטימיזציה ובתיאוריה של סיבוכיות. היא NP-קשה, וגרסת ההכרעה שלה היא NP-שלמה. משמעות זה היא שלא ידוע על אלגוריתם מהיר שמחשב תמיד את הכיסוי המינימלי לכל הקלטים.
נגיד U = {1,2,3,4,5} ו־S = {{1,2,3}, {2,4}, {3,4}, {4,5}}. איחוד כל קבוצות S הוא U. הכיסוי הקטן ביותר במקרה הזה הוא {{1,2,3}, {4,5}}.
ניתן לנסח את הבעיה כבעיית תכנון ליניארי בשלמים (תכנון ליניארי עם משתנים שלמים). הניסוח הזה שימושי כשמנסים לבנות שיטות קירוב מתמטיות.
קיים אלגוריתם חמדני פשוט לקירוב. בכל צעד הוא בוחר את הקבוצה שב־S שמכסה הכי הרבה איברים שלא כוסו עדיין. חוזרים עד שכל U כוסה. יחס הקירוב של החמדני הוא H(n), המספר ההרמוני עבור n = |U|, והוא מקיים H(n) ≤ ln(n)+1. כלומר, הפתרון שהחמדני מוצא לא גדול בהרבה מהאופטימום ביחס ל־log של גודל הבעייה. בנוסף אפשר להשיג קירוב טוב גם בעזרת תכנון ליניארי ואז עיגול אקראי של הפתרון הלא־שלם.
בעיית הכיסוי משמשת דוגמה בסיסית לבעיות אופטימיזציה בדידות. היא עזרה בפיתוח טכניקות מרכזיות בתחום האלגוריתמים המקורבים.
יש קבוצה של פריטים שנקראת U. יש גם אוסף של קבוצות קטנות שנקרא S. כל קבוצה ב־S מכילה חלק מהפריטים ב־U. כיסוי הוא בחירה של קבוצות מ־S כך שכל הפריטים ב־U יהיו כלולים לפחות בקבוצה אחת.
נניח U = {1,2,3,4,5}. הקבוצות ב־S הן: {1,2,3}, {2,4}, {3,4} ו־{4,5}. אם בוחרים את {1,2,3} ואת {4,5}, אז כל המספרים מ־U כלולים. זו בחירה קטנה וטובה.
יש שיטה פשוטה שנקראת אלגוריתם חמדני. כל פעם בוחרים את הקבוצה שמכסה הכי הרבה פריטים שעדיין לא כוסו. חוזרים עד שכיסו את כל U. השיטה נותנת פתרון קרוב לטוב, אבל לא תמיד מושלם.
מחשבים גם משתמשים בדרכים מתמטיות מתוחכמות יותר. למשל משתמשים בתכנון ליניארי ואז עושים עיגול אקראי, כדי לקבל פתרון טוב יותר במקרים מסוימים.
תגובות גולשים