אסתר ארקין

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

ביוגרפיה

גדלה בתל אביב, ולמדה בתיכון עירוני י"ד.^[1]

ב-1981 ארקין השלימה לימודי תואר ראשון במתמטיקה באוניברסיטת תל אביב. המשיכה את לימודיה באוניברסיטת סטנפורד, שם סיימה לימודי תואר שני בחקר ביצועים ב-1983 ודוקטורט ב-1986. תזת הדוקטורט שלה, Complexity of Cycle and Path Problems in Graph, נכתבה בהנחיית כריסטוס פאפאדימיטריו.

בשנים 1986–1991 עבדה באוניברסיטת קורנל, והגיע לדרגת פרופסור מן המניין אורחת.

ב-1995 עבדה מספר חודשים באוניברסיטת תל אביב כפרופסור חבר אורחת.

החל מ-1991 ארקין חברת סגל הפקולטה למתמטיקה יישומית וסטטיסטיקה באוניברסיטת סטוני ברוק.^[2]^[3]

חיים אישיים

נשואה לג'וזף מיטשל (אנ'), פרופסור למדעי המחשב שגם משויך לאוניברסיטת סטוני ברוק.^[1]

ממחקריה

בעיות תזמון של בירורקרט עצלן

ב-1999 ארקין פרסמה מאמר העוסק בתזמון משימות אופטימלי (אנ') ל"בירוקרט עצלן", שרוצה להיות הכי פחות יעיל שאפשר. הבירוקרט נדרש להיות נוכח במשך שעות מסוימות במשרד, וכל עוד יש משימות הניתנות לביצוע, הוא חייב לבצע עבודה כלשהי. לכל משימה יש חלון זמן שבו ניתן לבצעה, וערך מסוים שהשלמתה יביא למעסיק. הבירוקרט בוחר את המשימות וסדר ביצוען במטרה למקסם את הזמן שבו הוא אינו עובד (כי אין משימות הניתנות לביצוע), ולמזער את ערך המשימות שהוא כן יבצע (מתוך טינה למעסיק שלו). המאמר של ארקין ושותפיה מנסח את הבעיה בצורה פורמלית, ומנתח את סיבוכיות הבעיה.^[4]^[5]

המאמר ממחיש את הבעיה עם הדוגמה הבאה:^[6]

השעה 15:00, ודילברט מחויב להיות במשרד עד 17:00. אם לדילברט יש משימה, הוא חייב לבצע אותה (אחרת יפוטר). אם לדילברט יש מספר משימות, הוא רשאי לבחור איזה משימה לבצע.
לדילברט יש 2 משימות: אחת דורשת 10 דקות, והשנייה דורשת שעה. בנוסף, הוא יודע שב-15:15 יזומן לפגישה באורך 45 דקות. אם דילברט יתחיל קודם כל עם המשימה שאורכה 10 דקות, הוא יוכל ללכת לפגישה ב-15:15 עד 16:00, ואז לעבוד על המשימה שדורשת שעה בין 16:00 עד 17:00. מצד שני, אם ב-15:15 דילברט יהיה באמצע המשימה באורך שעה, הוא לא יצטרך ללכת לפגישה. ב-16:00 הוא יוכל להתחיל את המשימה באורך 10 דקות, ואז בין 16:10 ל-17:00 יהיה לו זמן פנוי. באופן טבעי, דילברט מעדיף את האופציה השנייה.

— מתורגם ממאמרה של ארקין ושותפים, "The Lazy Bureaucrat Scheduling Problem"

בעקבות מאמר זה, פורסמו מאמרים נוספים שהרחיבו את התיאוריה בנוגע ל"בירוקרטים עצלנים".^[7]^[8]^[9]

מדד להשוואת מצולעים

ארקין ושותפים פיתחו מדד להשוואת מצולעים, בדרך שנחשבת יעילה לחישוב. המדד פורסם במאמר מ-1989 הנקרא An efficiently computable metric for comparing polygonal shapes (מדד יעיל-לחישוב להשוואת מצולעים). המאמר הוא מאמרה המצוטט ביותר של ארקין, עם מעל ל-1,000 ציטוטים (נכון לנובמבר 2023). המאמר ממשיך להיות מצוטט גם כ-25 שנים לאחר פרסומו המקורי.^[10]

המדד משמש לחיפוש תמונות,^[11]^[12] מערכות ראיה ממוחשבת,^[10] מערכות מידע גאוגרפי^[13]^[14] ועוד.^[15]

המדד

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

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

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

לאחר יצירת הפונקציה התואמת למצולע, ניתן להשתמש בכלים מתמטיים מוכרים להשוואת פונקציות. ארקין ושותפיה בחרו להשתמש במטריקת $L^{p}$ .

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

אסתר ארקין, באתר פרויקט הגנאלוגיה במתמטיקה
אסתר ארקין, באתר dblp
אסתר ארקין, באתר גוגל סקולר
אסתר ארקין, באתר Academia.edu
אסתר ארקין, באתר IEEE

Esther Arkin | Department of Computer Science, www.cs.stonybrook.edu

הערות שוליים

^ ^1.0 ^1.1 אודות - אסתר ארקין, באתר פייסבוק
^ Esther Arkin | Department of Computer Science, www.cs.stonybrook.edu
^ M. O. Sztainberg, E. M. Arkin, M. A. Bender and J. S. B. Mitchell, "Theoretical and experimental analysis of heuristics for the "freeze-tag" robot awakening problem," in IEEE Transactions on Robotics, vol. 20, no. 4, pp. 691-701, Aug. 2004, doi: 10.1109/TRO.2004.829439. מכיל תיאור קצר על כותבי המאמר, כולל אסתר ארקין.
^ Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, Steven S. Skiena, The Lazy Bureaucrat Scheduling Problem, Information and Computation 184, 2003-07, עמ' 129–146 doi: 10.1016/S0890-5401(03)00060-9
^ Abrahams, Marc (2010-02-09). "Lazy bureaucrats, burden or blessing?". The Guardian (באנגלית בריטית). ISSN 0261-3077. נבדק ב-2023-10-28.
^ Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, Steven S. Skiena, The Lazy Bureaucrat Scheduling Problem, Information and Computation 184, 2003-07, עמ' עמוד 2 ב-PDF doi: 10.1016/S0890-5401(03)00060-9
^ Laurent Gourvès, Jérôme Monnot, Aris T. Pagourtzis, The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design, Fundamentals of Computation Theory, Lecture Notes in Computer Science, Springer, 2013, עמ' 171–182 doi: 10.1007/978-3-642-40164-0_18
^ Ling Gai, Guochuan Zhang, Online lazy bureaucrat scheduling with a machine deadline, Journal of Combinatorial Optimization 35, 2018-02-01, עמ' 530–537 doi: 10.1007/s10878-017-0180-7
^ Ling Gai, Guochuan Zhang, On lazy bureaucrat scheduling with common deadlines, Journal of Combinatorial Optimization 15, 2008-02-01, עמ' 191–199 doi: 10.1007/s10878-007-9076-2
^ ^10.0 ^10.1 Esther M. Arkin, L. Paul Chew, Daniel P. Huttenlocher, Klara Kedem, Joseph SB Mitchell, An efficiently computable metric for comparing polygonal shapes, 1989
^ Yong Rui, Thomas S. Huang, Shih-Fu Chang, Image Retrieval: Current Techniques, Promising Directions, and Open Issues, Journal of Visual Communication and Image Representation 10, 1999-03-01, עמ' 39–62 doi: 10.1006/jvci.1999.0413
^ Remco C. Veltkamp, Michiel Hagedoorn, State of the Art in Shape Matching, London: Springer, 2001, Advances in Pattern Recognition, עמ' 87–119, מסת"ב 978-1-4471-3702-3. (באנגלית)
^ Yongyang Xu, Zhong Xie, Zhanlong Chen, Mingyu Xie, Measuring the similarity between multipolygons using convex hulls and position graphs, International Journal of Geographical Information Science 35, 2021-05-04, עמ' 847–868 doi: 10.1080/13658816.2020.1800016
^ Jiyoung Kim, Kiyun Yu, Yoonsik Bang, A multi‐criteria decision‐making approach for geometric matching of areal objects, Transactions in GIS 22, 2018-02, עמ' 269–287 doi: 10.1111/tgis.12307
^ Google Scholar, scholar.google.com

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

38622754אסתר ארקין

[:1-1] 1.0 ^1.1 אודות - אסתר ארקין, באתר פייסבוק

[2] Esther Arkin | Department of Computer Science, www.cs.stonybrook.edu

[3] M. O. Sztainberg, E. M. Arkin, M. A. Bender and J. S. B. Mitchell, "Theoretical and experimental analysis of heuristics for the "freeze-tag" robot awakening problem," in IEEE Transactions on Robotics, vol. 20, no. 4, pp. 691-701, Aug. 2004, doi: 10.1109/TRO.2004.829439. מכיל תיאור קצר על כותבי המאמר, כולל אסתר ארקין.

[4] Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, Steven S. Skiena, The Lazy Bureaucrat Scheduling Problem, Information and Computation 184, 2003-07, עמ' 129–146 doi: 10.1016/S0890-5401(03)00060-9

[5] Abrahams, Marc (2010-02-09). "Lazy bureaucrats, burden or blessing?". The Guardian (באנגלית בריטית). ISSN 0261-3077. נבדק ב-2023-10-28.

[6] Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, Steven S. Skiena, The Lazy Bureaucrat Scheduling Problem, Information and Computation 184, 2003-07, עמ' עמוד 2 ב-PDF doi: 10.1016/S0890-5401(03)00060-9

[7] Laurent Gourvès, Jérôme Monnot, Aris T. Pagourtzis, The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design, Fundamentals of Computation Theory, Lecture Notes in Computer Science, Springer, 2013, עמ' 171–182 doi: 10.1007/978-3-642-40164-0_18

[8] Ling Gai, Guochuan Zhang, Online lazy bureaucrat scheduling with a machine deadline, Journal of Combinatorial Optimization 35, 2018-02-01, עמ' 530–537 doi: 10.1007/s10878-017-0180-7

[9] Ling Gai, Guochuan Zhang, On lazy bureaucrat scheduling with common deadlines, Journal of Combinatorial Optimization 15, 2008-02-01, עמ' 191–199 doi: 10.1007/s10878-007-9076-2

[:0-10] 10.0 ^10.1 Esther M. Arkin, L. Paul Chew, Daniel P. Huttenlocher, Klara Kedem, Joseph SB Mitchell, An efficiently computable metric for comparing polygonal shapes, 1989

[11] Yong Rui, Thomas S. Huang, Shih-Fu Chang, Image Retrieval: Current Techniques, Promising Directions, and Open Issues, Journal of Visual Communication and Image Representation 10, 1999-03-01, עמ' 39–62 doi: 10.1006/jvci.1999.0413

[12] Remco C. Veltkamp, Michiel Hagedoorn, State of the Art in Shape Matching, London: Springer, 2001, Advances in Pattern Recognition, עמ' 87–119, מסת"ב 978-1-4471-3702-3. (באנגלית)

[13] Yongyang Xu, Zhong Xie, Zhanlong Chen, Mingyu Xie, Measuring the similarity between multipolygons using convex hulls and position graphs, International Journal of Geographical Information Science 35, 2021-05-04, עמ' 847–868 doi: 10.1080/13658816.2020.1800016

[14] Jiyoung Kim, Kiyun Yu, Yoonsik Bang, A multi‐criteria decision‐making approach for geometric matching of areal objects, Transactions in GIS 22, 2018-02, עמ' 269–287 doi: 10.1111/tgis.12307

[15] Google Scholar, scholar.google.com

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]