הצגת המקור של הדף "בעיית k המרכזים"

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

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

==הגדרה פורמלית==
* יהי G [[גרף מלא]] [[גרף (תורת הגרפים)#סוגי גרפים|לא מכוון]] [[גרף ממושקל|ממושקל]] ותהיינה V ו-E קבוצת הצמתים והקשתות בגרף בהתאמה. יהי המרחק <math>d(V_i,V_j) \in N</math> המרחק בין הצמתים i ו-j המקיים את אי-שוויון המשולש. 
* יש למצוא תת-קבוצה S של V בגודל k כך שהערך המקסימלי (על-פני <math>\ v \in V</math>) של כל ערכי המינימום <math>\min_{s \in S} d(v,s)</math>, הוא הקטן ביותר האפשרי.

==[[סיבוכיות]]==
בעיית k המרכזים ידועה כבעיה [[NP (סיבוכיות)#NP-קושי ובעיות NP-שלמות|NP שלמה]] מכיוון שניתן באמצעות [[רדוקציה חישובית]] להראות שבהינתן פתרון לבעיית k המרכזים ניתן למצוא פתרון ל[[בעיית הקבוצה השולטת]] (Dominating set) בגרף כלשהו{{הערה|1=[http://books.google.co.il/books?id=EILqAmzKgYIC&dq=Approximation+Algorithms&printsec=frontcover&source=bn&hl=iw&ei=B-drS9ToF8bKjAeQk831BQ&sa=X&oi=book_result&ct=result&resnum=4&ved=0CCAQ6AEwAw#v=onepage&q=&f=false Approximation algorithms], Vijay Vazirani, עמודים 47-48}}.

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

אלגוריתם קירוב נוסף בעל שגיאה דומה מבצע רדוקציה לבעיית מציאת [[קבוצה בלתי תלויה (תורת הגרפים)|קבוצה בלתי תלויה]] מקסימלית (Maximal independent set) בגודל k בגרפים המתקבלים על ידי הוספת צומתי G לקבוצה הריקה, העלאת G בחזקה (Power Graphs) ומציאת הגרף הקטן ביותר עבורו ניתן למצוא [[קבוצה שולטת]] מלאה בגודל k.{{הערה| 
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).}}

==הערות שוליים==
{{הערות שוליים}}


[[קטגוריה:אופטימיזציה רציפה]]
[[קטגוריה:בעיות NP-שלמות]]
[[קטגוריה:תורת הגרפים]]