נולד ברבאט שבמרוקו. אחיו של דוד לוי. בגיל שבע עלה ארצה עם משפחתו. לאחר שגדל והתחנך בלוד, עשה את שירותו הצבאי במשמר הגבול. ומיד עם שחרורו החל לעבוד בתעשייה האווירית, שם נבחר לתפקיד יו"ר ועד העובדים של הארגון הגדול במדינה.
בשנת 1978 בגיל 28 בלבד, נבחר לוי לראשונה למועצת עיריית לוד וכיהן בתפקיד סגן ראש העירייה. בשנת 1983 הצליח להיבחר לתפקיד ראש עיריית לוד מטעם הליכוד, תפקיד בו החזיק עד לשנת 1996. התחום העיקרי בו פעל היה תחום החינוך והתרבות וביוזמתו נבנו בתי ספר ומתנ"סים רבים. במקביל לתפקידו כראש עירייה, נבחר לוי בשנת 1989 לתפקיד יו"ר מרכז השלטון המקומי בישראל וכחבר בדירקטוריון של החברה למשק וכלכלה.
בשנת 1996, במסגרת מפלגת גשר שהקים אחיו דוד לוי התמודד לכנסת ונבחר כחבר הכנסת ה-14, ברשימת הליכוד-גשר-צומת. בהמשך נבחר אף לכנסת ה-15 ברשימת ישראל אחת (הרשימה המשותפת של מפלגת העבודה, גשר ומימד). הוא מילא שורה של תפקידים בכנסת, כיושב ראש ועדת העבודה והרווחה, כחבר בוועדות הפנים, הכספים, איכות הסביבה, הבריאות ועוד, והגיע עד לתפקיד סגן יושב ראש הכנסת ה-15. מרבית החקיקה שקידם הייתה בתחום החברתי. מאז נבחר לוי כחבר כנסת ועזב את תפקידו כראש העירייה, התדרדרה העיר עד אשר מונתה לה ועדה קרואה.
בשנת 2002 נענה להפצרותיהם של אנשי חינוך, מנהלי בתי ספר ומנהלי מתנ"סים שקראו לו לחזור ולהציל את לוד. בבחירות שהתקיימו בחודש מאי 2002, נבחר שוב לתפקיד ראש עיריית לוד ברוב גדול, והתפטר מהכנסת.
בארבעת חודשי כהונתו המחודשת כראש העיר ועד מותו, הצליח להביא לכך שממשלת ישראל תכיר בצרכים של לוד ברמה הלאומית, לא רק המוניציפלית. הופעלה תוכנית רב צדדית לקידום והבראת העיר, שבמסגרתה משרד ראש הממשלה לקח על עצמו את האחריות לתיאום בין כל הגופים השונים.
מיד עם כניסתו לתפקיד ראש העירייה, החל בביצוע עבודות שונות לרווחת תושביה בתחומים שונים הכוללים בין היתר: ניקיון ושיפוצים בשכונות ובכניסות לעיר, קרצוף וריבוד כבישים, הגברת הביטחון האישי של התושבים, שיפוץ מוסדות החינוך ותיקון ליקויי הבטיחות.
בליל שבת, 11 באוקטובר 2002, הלך לוי לעולמו בגיל 52, לאחר שלקה בליבו. הוא הותיר אחריו את אשתו כרמלה, שלושה ילדים וארבעה נכדים.
על שמו נקרא תיכון בשכונת גני אביב שבלוד וכן היכל התרבות של העיר.
רבט
שמעון אגרנט
שמעון אגרנט (5 בספטמבר 1906 – 10 באוגוסט 1992) היה הנשיא השלישי של בית המשפט העליון.
קורות חיים.
אגרנט נולד בלואיוויל שבארצות הברית, בט"ו באלול ה'תרס"ו, 1906, לד"ר אהרון יוסף אגרנט (1881–1946), יו"ר הסתדרות רופאי השיניים בישראל ופעיל ציוני, ולפנינה בת שמעון שניצר. הוריו היגרו לארצות הברית מחיסלוויצ'י שברוסיה זמן קצר לפני לידתו. אביו התפרנס מהוראת עברית והיה ציוני שביקש לעלות לארץ ישראל. אגרנט גדל בשיקגו, למד בבתי ספר יהודיים ולזמן מה למד בגמנסיה העברית הרצליה. הוא למד באוניברסיטת שיקגו ובמקביל לימד עברית בבית ספר יהודי בעיר והיה אחראי על שיעורי העברית בבית הספר היהודי בו לימד. כן היה פעיל בארגון אבוקה בשיקגו.
בשנת 1926 קיבל תואר ראשון. בפילוסופיה מאוניברסיטת שיקגו ובהמשך קיבל תואר במשפטים מאותה אוניברסיטה. ב-1930 הוא עלה לארץ ישראל עם הוריו, עבר את מבחני ההסמכה לעורכי דין זרים באפריל 1931 וקיבל רישיון עריכת דין באפריל 1932. את ההתמחות עשה בירושלים ולאחריה עסק כעורך דין פרטי בחיפה. בין השאר עבד עבור ועד הקהילה בחיפה בסיוע לעולים שנכנסו לארץ ישראל נגד חוקי המנדט הבריטי ונכלאו בכלא עכו.
בסוף שנות השלושים נישא לכרמל פרידלנדר, בת לישראל פרידלנדר ולליליאן לבית בנטוויץ'. דודה של אשתו, אחי אמה, נורמן בנטוויץ', סייע לאגרנט לבחור במשרת שופט, ואף המליץ עליו בפני הנציב העליון. ב-1940, תחת שלטון המנדט הבריטי, מונה לשופט בבית המשפט השלום בחיפה וב-1948 לנשיא בית המשפט המחוזי בחיפה. עם ייסודו של בית המשפט העליון של מדינת ישראל בשנת 1948 היה שמו של אגרנט בין השמות הראשונים שהועלו לשמש בו כשופט, אולם הוא לא נמנה בין חמשת השופטים הראשונים (עקב העובדה שרק זמן קצר לפני כן מונה לבית המשפט המחוזי, והשופט חשין, שנבחר במקומו, היה שופט מחוזי ותיק יחסית). בדצמבר 1948 מונה לשופט בבית המשפט העליון בפועל וב-2 בינואר 1950 מונה במינוי של קבע.
כן שימש בשנים 1954–1966 במשרת פרופסור אורח למשפט פלילי באוניברסיטה העברית.
ב-29 בפברואר 1960 מונה אגרנט לממלא מקום קבוע לנשיא בית המשפט העליון. ב-18 במרץ 1965 התמנה לנשיא בית המשפט העליון וכיהן בתפקיד זה עד לפרישתו ב-5 בספטמבר 1976.
אגרנט הוא חתן פרס ישראל למשפט לשנת ה'תשכ"ח.
בשנותיו בבית המשפט העליון כתב אגרנט פסקי דין רבים אשר דנו בשאלות מכריעות והרות גורל (כהרשעתו של אדולף אייכמן), ושימש אב בית דין במשפטים רבים אשר עיצבו את דמותה המשפטית של מדינת ישראל.
פסק הדין הידוע ביותר והמצוטט ביותר של אגרנט הוא פסק דינו בבג"ץ קול העם, בו דן ביסס אגרנט באריכות את חופש הביטוי כזכות עילאית במשפט החוקתי של ישראל, וקבע את מבחן "הוודאות הקרובה" הנדרש משיקולי ביטחון כדי לגבור על חופש הביטוי. פסק-דין ידוע אחר של אגרנט הוא פסק דין ירדור.
בשנת 1962 מונה לעמוד בראש 'ועדת המשפטנים בדבר סמכויות היועץ המשפטי לממשלה' שכונתה על שמו ועדת אגרנט (הראשונה). הוועדה בראשותו הציגה לממשלה בחוות דעתה את מבנה סמכויותיו של היועץ, יחסיו עם שר המשפטים ועם הממשלה, ותוקפה של חוות דעתו ביחס לממשלה וביחס לרשויותיה המנהליות. מסקנותיה של ועדת אגרנט השפיעו על הגדרת תפקיד היועץ המשפטי לממשלה עשרות שנים קדימה והן עדיין מהוות נושא לדיון משפטי ער.
בשנת 1973 מונה אגרנט לעמוד בראש ועדת החקירה הממלכתית (שכונתה בהתאם ועדת אגרנט) לחקר נסיבות פריצתה של מלחמת יום הכיפורים. פרסום הדוח הראשוני היה באפריל 1974 והוועדה הטילה את האחריות לכשלים המודיעיניים על הדרג המבצעי, והמליצה על סיום כהונתם של הרמטכ"ל וראש אמ"ן. היא לא ביקרה את ראשי הדרג המדיני, משה דיין וגולדה מאיר. למרות זאת לאחר מספר שבועות התפטרה גולדה מאיר מראשות הממשלה.
סוגיה שצצה לאחר מספר שנים היא האם אגרנט ידע על פגישתה של גולדה מאיר עם חוסיין, מלך ירדן, ב-25 בספטמבר 1973, במסגרתה הזהיר חוסיין את ישראל מפני התקפה קרובה מצד מצרים וסוריה. אגרנט טען שלא ידע על פגישה זו אך צבי זמיר טען שאכן ידע.
בשנות חייו האחרונות, החל משנת 1988, כיהן אגרנט כנשיא האגודה לזכויות האזרח.
אגרנט נפטר בי"א באב ה'תשנ"ב, 10 באוגוסט 1992, בן 86, ונקבר בירושלים. הוא הותיר אחריו שלושה בנים ושתי בנות. אורית סון היא נכדתו.
הכיכר בין בית המשפט העליון למשרד החוץ בירושלים נקראת על שמו.
ספר יובל לכבודו.
בשנת 1986 יצא לכבודו של שמעון אגרנט ספר יובל:
מע&quot;ר
אלגוריתם קירוב
אלגוריתם קירוב (באנגלית: approximation algorithm) הוא אלגוריתם שמוצא פתרון שאינו בהכרח פתרון אופטימלי לבעיה נתונה, אלא פתרון שקרוב לפתרון אופטימלי. אלגוריתמים אלו שימושיים במיוחד בבעיות שהאלגוריתמים הידועים לפיתרונן הם בסיבוכיות גבוהה, ובפרט בבעיות NP קשות, קבוצת הבעיות NP קשות שקיים להם אלגוריתם קירוב נקראת APX, ניתן להוכיח שיש בעיות שאין להם אלגוריתם קירוב אלא אם כן P=NP.
על פי רוב מודדים קירוב של אלגוריתם בהתאם ליחס בין הפתרון שנמצא על ידי האלגוריתם לבין הפתרון האופטימלי. נאמר כי אלגוריתם קירוב לבעיה משיג יחס קירוב של formula_1 (לפעמים נאמר גם אלגוריתם formula_1-מקרב) אם הפתרון המושג על ידי האלגוריתם קטן מ-formula_1 פעמים הפתרון האופטימלי לבעיה (אם הבעיה היא בעיית מינימיזציה) או גדול מהחלק ה-formula_1 של הפתרון האופטימלי לבעיה (אם הבעיה היא בעיית מקסימיזציה).
סוגי אלגוריתמי קירוב.
ישנם כמה סוגים של אלגוריתמי קירוב, שנבדלים ביניהם בסוג הקירוב שהם מציעים ובסיבוכיות שלהם:
קירוב באמצעות קבוע.
אלגוריתמי קירוב אלו מציעים קירוב בפער של מכפלה במספר קבוע מהערך האופטימלי, למשל השמה של לפחות חצי מהערך המקסימלי בבעיית התרמיל, בזמן פולינומי לגודל הקלט. אלגוריתמים חמדניים שנותנים קירוב הם מסוג זה.
סכמת קירוב פולינומית (PTAS).
אלגוריתמי קירוב מסוג סכמת קירוב פולינומית מקבלים formula_5 כלשהו כקלט ומתייחסים אליו כקבוע, ומציעים קירוב של מכפלה של formula_6 מהערך האופטימלי (או formula_7 בבעיות מינימום). כל זה בזמן פולינומי לגודל הקלט, חשוב לציין שזה עלול להיות אקספוננציאלי ביחס ל-formula_8 (הוא יכול להיות החזקה).
תת קבוצה של אלגוריתמים אלו היא סכמת קירוב פולינומית מלאה (FPTAS). באלגוריתמים אלו הסיבוכיות פולינומית גם בגודל הקלט וגם ב-formula_8. קירוב כזה קיים לבעיית תרמיל הגב למשל.
דוגמה לאלגוריתם קירוב.
בעיית הסוכן הנוסע בגרף מטרי מוגדרת כבעיית מציאת מסלול המילטוני בגרף ממושקל: דהיינו מסלול שעובר בכל צומת בדיוק פעם אחת וחוזר לצומת הראשון, ומשקלו מינימלי.
בעיה זו היא NP-קשה, אולם ניתן לקרב אותה באופן הבא (האלגוריתם של קריסטופידס):
אלגוריתם:
מוצאים עץ פורש מינימלי בגרף. בוחרים צומת כלשהו כשורש, ומטיילים לעומקו של העץ, במסלול ששקול לחיפוש לעומק. כאשר אנו מגלים שאנו חוזרים לצומת בו כבר היינו, נבצע "קיצור דרך", דהיינו, נמשיך ישירות לצומת הבא ברשימה - וזאת עד שביקרנו בכל הצמתים ונחזור לצומת שממנו התחלנו.
טיעון קירוב:
על מנת להיווכח שהאלגוריתם המתואר לעיל הוא אלגוריתם קירוב, יש לבחון את הפתרון שנמצא ביחס לפתרון האופטימלי.