בעיית כיסוי קבוצות
בעיה קלאסית בקומבינטוריקה, מדעי המחשב, אופטימיזציה וסיבוכיות הבעיה נכללת ברשימת 21 הבעיות ה-NP-שלמות של קארפ / ויקיפדיה האנציקלופדיה encyclopedia
בעיית כיסוי קבוצות (באנגלית: Set Cover Problem) היא בעיה קלאסית בקומבינטוריקה, מדעי המחשב, אופטימיזציה וסיבוכיות. הבעיה נכללת ברשימת 21 הבעיות ה-NP שלמות של קארפ.
בעיית כיסוי הקבוצות היא בעיה חשובה בתחום אלגוריתמי קירוב. היא בעיה ש"לימודה הוביל לפיתוח טכניקות יסודיות לתחום הכולל" של אלגוריתמים מקורבים.[1]
הבעיה היא: נתונה קבוצה סופית של קבוצות סופיות, שאיחודן הוא הקבוצה . יש למצוא תת-קבוצה של בגודל מינימלי, שאיחוד הקבוצות בה הוא . כלומר יש למצוא את הכיסוי הקטן ביותר לקבוצה שהוא תת-כיסוי של .
שאלה זו היא NP-קשה; וגרסת בעיית ההכרעה שלה היא NP-שלמה.[2]
הבעיה הזו היא דוגמה אופיינית וחשובה של בעיית אופטימיזציה בדידה. תכונה חשובה של בעיה בסיסית זו היא שניתן למצוא באופן יעיל קירוב סביר לאופטימום שלה - ניתן למצוא באופן יעיל פתרון לבעיה הקרוב לפתרון האופטימלי, בסיבוכיות שתהיה בסדר גודל של הלוגריתם של גודל הקבוצה שאותה יש לכסות.