Skip to Content

Sponsors

No results

Tags

No results

Types

No results

Search Results

Events

No results
Search events using: keywords, sponsors, locations or event type
When / Where
All occurrences of this event have passed.
This listing is displayed for historical purposes.

U-M Industrial & Operations Engineering pres.

IOE Lunch & Learn Seminar Series: Niusha Navidi, U-M IOE

Adaptive Submodular Ranking and Routing

photo of Niusha Navidi photo of Niusha Navidi
photo of Niusha Navidi
This event is open to all IOE PhD students, faculty, and staff. Lunch will be provided. In order to get an accurate count for food, please RSVP by Thursday, January 16, 2020.

Title:
Adaptive Submodular Ranking and Routing

Abstract:
We study a general stochastic ranking problem where an algorithm needs to adaptively select a sequence of elements so as to “cover” a random scenario (drawn from a known distribution) at minimum expected cost. The coverage of each scenario is captured by an individual submodular function, where the scenario is said to be covered when its function value goes above a given threshold. We obtain a logarithmic factor approximation algorithm for this adaptive ranking problem, which is the best possible (unless P = NP). This problem unifies and generalizes many previously studied problems with applications in search ranking and active learning. The approximation ratio of our algorithm either matches or improves the best result known in each of these special cases. Furthermore, we extend our results to an adaptive vehicle routing problem, where costs are determined by an underlying metric. This routing problem is a significant generalization of the previously-studied adaptive traveling salesman and traveling repairman problems. Our approximation ratio nearly matches the best bound known for these special cases. Finally, we present experimental results for some applications of adaptive ranking.

Bio:
Fatemeh Navidi is a fifth year PhD student in the Department of Industrial and Operations Engineering at the University of Michigan, advised by Professor Viswanath Nagarajan. Her research interests include Combinatorial Optimization Under Uncertainty, Design and Analysis of Adaptive Approximation Algorithms and Machine Learning.
photo of Niusha Navidi photo of Niusha Navidi
photo of Niusha Navidi
Report Event As Inappropriate Contact Event Organizers
Back to Main Content