נגדיר את בעיית האופטימיזציה הבאה, WMAXCUT. קלט: גרף G = (V, E) לא מכוון ופונקציה w : E ℝ+ המתאימה משקל חיובי ל…

נגדיר את בעיית האופטימיזציה הבאה, WMAXCUT. קלט: גרף G = (V, E) לא מכוון ופונקציה $w : E \to ℝ+$ המתאימה משקל חיובי לכל קשת. מטרה : למצוא חתך מושרה בגרף שמשקלו מקסימלי. יהי G = (V, E), w קלט לבעיה, ונסמן ב W את סך כל המשקלים בגרף, כלומר$, W = Σ_{e\in E} w(e)$. מהו הערך הגדול ביותר $α \in [0,1]$ עבורו ידוע שקיים חתך בגרף במשקל $αW$ ? שימו לב כי עבור הערך שתבחרו יש להוכיח כי קיים חתך כדרוש, וגם לא ידוע שקיים חתך גדול יותר.