דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
גלעד קותיאל (הרצאה סמינריונית לדוקטורט)
event date icon
יום רביעי, 20.02.2019, 15:00
event location icon
Taub 601
event speaker icon
מנחה: Prof. R. Schawrtz and Dr. Dror Rawitz
In the Maximum Carpool Matching problem we seek for the best way a group of people can share their ride based on their personal preferences (music, smoking, etc...). Submodularity is a property of set functions. The problem of maximizing a submodular function appears in many applications such as viral marketing, information gathering, image segmentation, document summarization, and speeding up satisfiability solvers. Both the Maximum Carpool Matching and the Submodular Function Maximization problems are NP-hard, and thus, no efficient algorithm is known for them. In this talk we will present an approximation algorithm for Submodular Maximization and will show how Submodular Maximization can be used to design an approximation algorithm for the Maximum Carpool Matching problem.