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