Computer Science Colloquia: Sun, Nov 6 at 11:00 - Niv Buchbinder
Niv Buchbinder
Dear all,
Next week we will have our first seminar for this semester. I will be the first speaker for the semester (see abstract below). You can view the upcoming talks of the seminar at:
See you,
Niv Buchbinder.
%%%%%%%%%%%%%%%%%%%%%%
Computer Science Colloquia - Open University of Israel
%%%%%%%%%%%%%%%%%%%%%%
Time: Sunday, November 6, at 11:00-12:00
Place: Visitor center 194, Open University.
Speaker: Niv Buchbinder, Open University.
-------
Title: Secretary Problems and Online Auctions (Secretary Problems via Linear Programming)
-----
Abstract:
In the classical secretary problem an employer would like to choose the best candidate among n competing candidates that arrive in a random order. This basic concept of n elements arriving in a random order and irrevocable decisions made by an algorithm have been explored extensively over the years, and used for modeling the behavior of many processes. Our main contribution is a new linear programming technique that we introduce as a tool for obtaining and analyzing mechanisms for the secretary problem and its variants. Capturing the set of mechanisms as a linear polytope holds the following immediate advantages.
1. Computing the optimal mechanism reduces to solving a linear program.
2. Proving an upper bound on the performance of any mechanism reduces to finding a feasible solution to the dual program.
3. Exploring variants of the problem is as simple as adding new constraints, or manipulating the objective function of the linear program.
We demonstrate the applicability of these ideas in several settings including online auctions.
This is a joint work with Kamal Jain and Mohit Singh.