‏290.00 ₪

תוכן עניינים

פרק 1 (מבוא)

            1.1 - במה עוסק הסמינר?                                                                 עמ' 2

            1.2 - בעיות אופטימיזציה                                                                 עמ' 4

            1.3 - בעיית הספיקות                                                                        עמ' 7

פרק 2 (אלגוריתמים דטרמיניסטיים)

            2.1 - האלגוריתמים החמדנים של ג'ונסון                                       עמ' 9

                        2.1.1 - האלגוריתם הראשון של ג'ונסון                               עמ' 9

                        2.1.2 - האלגוריתם השני של ג'ונסון                                    עמ' 14

            2.2 - חיפוש מקומי                                                                            עמ' 22

פרק 3 (אלגוריתמים אקראיים)

            3.1 - האלגוריתם Random                                                            עמ' 25

            3.2 - שיטת ההסתברויות המותנות                                     עמ' 26

            3.3 - האלגוריתם GenRandom                                                   עמ' 27

            3.4 - שיטת GenApprox                                                                עמ' 28

                        3.4.1 - אלגוריתם ¾-קירוב                                     עמ' 30

                        3.4.2 - אלגוריתם Goemans-Williamson                  עמ' 35

            נספח (הוכחת הלמה מסעיף 2.1.2)                                        עמ' 64 

 ביבליוגרפיה                                                                                                עמ' 70

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

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

הפרק השני בסמינר מחולק לשלושה חלקים ועוסק בשלושה אלגוריתמים דטרמיניסטיים לפתרון הבעיה: שני האלגוריתמים שהוצגו על ידי ג'ונסון במאמר [3] משנת 1974, ואלגוריתם החיפוש המקומי.

האלגוריתם הראשון של ג'ונסון פועל על ידי בחירה סדרתית של ערכי המשתנים, כך שכל בחירה מביאה לשיפור מקסימלי במשקל הפסוקיות המסופקות. בסמינר מוכח שאלגוריתם זה פועל בזמן לינארי, ומוכח שמדובר באלגוריתם ½-קירוב ו-½-קירוב בלבד.

האלגוריתם השני של ג'ונסון מחוכם יותר מהאלגוריתם הראשון, ומקטין פי 2 את ערכה של פסוקית עבור כל ליטרל חופשי אשר נותר בה. (כיוון שעבור חצי מהשמות ערכי האמת, יביא ליטרל זה לסיפוק הפסוקית) בסמינר מוכח שאלגוריתם זה דורש גם הוא זמן ריצה לינארי, שמדובר באלגוריתם 2/3-קירוב, ו-2/3-קירוב בלבד. (ניתן לציין שעובדה זו חמקה מג'ונסון כאשר הציג את האלגוריתם. ג'ונסון טען כי מדובר באלגוריתם ½-קירוב בלבד, כמו האלגוריתם הראשון) הוכחת ההערכה ההדוקה לביצועי האלגוריתם מתבססת על ההוכחה המופיעה במאמר [2] משנת 1997, בו הוכחה טענה זו לראשונה, 23 שנים לאחר שהאלגוריתם הוצג על ידי ג'ונסון.

אחרון בפרק זה הוא אלגוריתם החיפוש המקומי. אלגוריתם זה כולל בחירת השמת ערכי אמת שרירותית והחלפת ערכו של משתנה יחיד לשיפור משקל הפסוקיות המסופקות מדי איטרציה עד להגעה לנקודת מקסימום מקומית, ממנה לא ניתן לשפר עוד את הפתרון על ידי החלפת ערכו של משתנה יחיד. מוכח כי אלגוריתם זה הוא אלגוריתם ½-קירוב, כאלגוריתם הראשון של ג'ונסון.

הפרק השלישי בסמינר עוסק במספר אלגוריתמים אקראיים לפתרון הבעיה המשיגים ביצועים טובים אף יותר מאלה הדטרמיניסטיים. בפרק מופיעה "שיטת ההסתברויות המותנות", שיטה כללית לדה-רנדומיזציה של אלגוריתמים אקראיים מסוימים ההופכת אותם לאלגוריתמים דטרמיניסטיים המבטיחים ביצועים השווים לביצועיהם הממוצעים לפני ההמרה. בפרק זה מוצגים חמישה אלגוריתמים: שני האלגוריתמים הפשוטים Random ו-GenRandom אשר בוחרים את השמת ערכי האמת באקראי לפי התפלגות נתונה, אלגוריתם ה-¾-קירוב של Goemans-Williamson אותו הציגו השניים במאמר

אלגוריתם ¾-קירוב פשוט נוסף המנצל את שיטתם של Goemans-Williamson באופן אחר, והאלגוריתם של Yannakakis, גם הוא אלגוריתם ¾-קירוב, אשר הופיע במאמר. ניתן להשתמש בשיטת ההסתברויות המותנות על מנת להפוך את כל האלגוריתמים הללו לדטרמיניסטיים.

ביבליוגרפיה לדוגמא (בעבודה האקדמית כ-20 מקורות אקדמיים באנגלית ובעברית)

1)      R. Battiti and M. Protasi, Approximate algorithms and heuristics for MAX-SAT, Handbook of combinatorial optimization , pp. 77-148

2)      J. Chen, D. K. Friesen and H. Zheng, Tight bound on the Johnson’s algorithm for Max-SAT, Proc. 12^th Annual IEEE Conf. On Computational Complexity , Ulm, Germany, pp. 274-281

3)      D.S. Johnson, Approximation algorithms for combinatorial problems, journal of Computer and System Sciences 9 , pp. 256-278