בעיית k המרכזים

בתורת הגרפים, בעיית k המרכזים היא בעיית אופטימיזציה, המבקשת להקים ברשת נתונה מספר קבוע מראש של "מרכזי שירות", כך שהמרחק של ה"לקוח" הרחוק ביותר מכל המרכזים יהיה קטן ככל האפשר.

פורמלית, הבעיה מקבלת גרף ממושקל בעל n צמתים ומטרתה למצוא תת-קבוצה בגודל k, המביא למינימום את המרחק בין כל צומת בגרף לאחד הצמתים בקבוצה k. האלגוריתמים הידועים לבעיה מניחים שהמרחקים בגרף מקיימים את אי-שוויון המשולש.

הגדרה פורמלית

• יהי G גרף מלא לא מכוון ממושקל ותהיינה V ו-E קבוצת הצמתים והקשתות בגרף בהתאמה. יהי המרחק ${\displaystyle d(V_{i},V_{j})\in N}$ המרחק בין הצמתים i ו-j המקיים את אי-שוויון המשולש.
• יש למצוא תת-קבוצה S של V בגודל k כך שהערך המקסימלי (על-פני ${\displaystyle \ v\in V}$) של כל ערכי המינימום ${\displaystyle \min _{s\in S}d(v,s)}$, הוא הקטן ביותר האפשרי.

סיבוכיות

בעיית k המרכזים ידועה כבעיה NP שלמה מכיוון שניתן באמצעות רדוקציה חישובית להראות שבהינתן פתרון לבעיית k המרכזים ניתן למצוא פתרון לבעיית הקבוצה השולטת (Dominating set) בגרף כלשהו^[1].

אלגוריתמי קירוב

קיימים מספר אלגוריתמי קירוב לבעיה. בשנת 1985 הראה טופילו גונזלס אלגוריתם חמדן הפותר את הבעיה עם שגיאת קירוב 2^[2] ובונה את הפלט S תוך שימוש ב-k איטרציות. באיטרציה הראשונה האלגוריתם בוחר צומת שרירותי ומוסיף אותו ל-S. לאחר מכן, בכל איטרציה בוחר האלגוריתם את הצומת הרחוק ביותר מצומת כלשהו ב-S ומוסיף אותו ל-S. זמן הריצה הכולל של האלגוריתם הוא (O(kn.

אלגוריתם קירוב נוסף בעל שגיאה דומה מבצע רדוקציה לבעיית מציאת קבוצה בלתי תלויה מקסימלית (Maximal independent set) בגודל k בגרפים המתקבלים על ידי הוספת צומתי G לקבוצה הריקה, העלאת G בחזקה (Power Graphs) ומציאת הגרף הקטן ביותר עבורו ניתן למצוא קבוצה שולטת מלאה בגודל k.^[3]

הערות שוליים

1. Approximation algorithms, Vijay Vazirani, עמודים 47-48
2. כלומר, אורך המסלול המקסימלי בו הוא לכל היותר פי 2 מאורך המסלול המקסימלי בפתרון האופטימלי.
3. Dorit S. Hochbaum & David B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM (JACM), 1986, Volume 33, Issue 3 (July 1986).