פרס פולקרסון

פרס פולקרסון (באנגלית: The Fulkerson Prize) הוא פרס המוענק עבור מאמרים מצטיינים בתחום המתמטיקה הדיסקרטית וממומן במשותף על ידי האגודה למיטוב מתמטי (MOS) והאגודה האמריקאית למתמטיקה (AMS). ניתן להעניק.עד שלושה פרסים בסך 1,500 דולר כל אחד בכנס הבין־לאומי של האגודה למיטוב מתמטי. במקור, הפרסים שולמו מתוך קרן הנצחה המנוהלת על ידי האגודה האמריקאית למתמטיקה שהוקמה על ידי חבריו של דלברט ריי פולקרסון המנוח כדי לעודד מצוינות מתמטית בתחומי המחקר שהודגמה בעבודתו. הפרסים ממומנים כעת על ידי קרן המנוהלת על ידי MPS.

פרס פולקרסון
Fulkerson Prize

תיאור	מאמר יוצא דופן מכל ענפי המתמטיקה הבדידה
מדינה
הגוף המעניק	האגודה האמריקאית למתמטיקה והאגודה למיטוב מתמטי
תקופת הפרס	1979–הווה (כ־45 שנים)
נקרא על שם	דלברט ריי פולקרסון
http://www.ams.org/profession/prizes-awards/ams-prizes/fulkerson-prize

זוכי הפרס

1979

• ריצ'רד קארפ על סיווג שלמות NP רבים וחשובים
• קנת אפל וולפגנג הוק על משפט ארבעת הצבעים
• פול סימור על הכללת משפט זרימה מקסימלית - חתך מינימלי למטרואיד

1982

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

1985

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

1988

• אווה טרדוש למציאת בעיית מחזור בסיבוכיות זמן
• נרנדרה קרמרקר האלגוריתם של קרמרקר עבור תכנון ליניארי

1991

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

1994

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

1997

• ג'ונג האן קים למציאת ניתוח אסימפטוטי של מספרי רמזי.

2000

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

2003

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

2006

• מנינדרה אגרוול, נארג' קיהל, ניטין סקסנה עבור מבחן AKS לראשוניות.
• מארק ג'רום, אליסטר סינקלייר, ואריק ויגודה עבור חישוב משוער.

2009

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

2012

• סנג'ייב ארורה, סתי ראו ואומש וזיראני על שיפור אלגוריתם קירוב מפריד ורטקס בעיות הקשורות מאת $O(\log n)$ to $O({\sqrt {\log n}})$.
• אנדרס ג'והנסון, ג'ף קאהן וואן וו לקביעת סף צפיפות הקצה שמעליו ניתן לכסות גרף מקרי על ידי עותקים לא צמודים של גרף קטן יותר נתון.
• לסלו לובאס ובלגז שזגאדי לאפיון ריבוי תת-גרפים ברצפים של גרף צפוף.

2015

• פרנסיסקו סנטוס לייל לדוגמה נגדית של השערת הירש.

2018

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

קישורים חיצוניים

מדיה וקבצים בנושא פרס פולקרסון בוויקישיתוף

• אתר האינטרנט הרשמי של פרס פולקרסון (באנגלית)
• פרס פולקרסון באתר האגודה למיטוב מתמטי (באנגלית)
• פרס פולקרסון באתר האגודה האמריקאית למתמטיקה (באנגלית)