Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Approximation Algorithms for the Maximum Carpool Matching and Submodular Maximization
event speaker icon
Gilad Kutiel (Ph.D. Thesis Seminar)
event date icon
Wednesday, 20.02.2019, 15:00
event location icon
Taub 601
event speaker icon
Advisor: 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.