MIME-Version: 1.0 Content-Location: file:///C:/5D19A4D4/file1684.htm Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset="us-ascii" תרגיל בית מספר 4

תרגיל בית מספר 4

<= o:p> 

<= o:p> 

1.    נסמ&= #1503; ב-MAX-3SAT(<= i>k) את בעיית MAX-3SAT המוגבלת לקל= 96; שבו כל משתנה מופיע לכל היותר k פעמים. הראו שיש קבו= 506; טבעי k וקבוע c < 1 כך שקשה לקרב את בעיית MAX-3SAT(k)= בפקטור של c + ε, לכל <= /span>ε > 0.

רמז: נצלו א= ת קיומם של גרפים מרחיבים חסומי דרגה.

2.    בהס&= #1514;מך על 1, הראו שקיים קבוע טבעי d וקבוע c > 1 כך שקשה לקרב את בעיי= 514; VERTEX-COVER בגרפים עם דרגה מרבית ל= 499;ל היותר d בפקטור c – ε, לכל <= /span>ε > 0.

3.    הרא&= #1493; שלכל ε > 0= קשה לקרב את בעיית MAX-COVERAGE בפקטור של (e-1)/e + &#= 949;.

4.    תנו קירוב בפקטו= 12; טוב מ-0.878 עבור בעיית MAX-2SAT= .

רמז: הוסיפ&= #1493; משתנה עזר שיציין את הערך "אמת".