Computer Science Colloquia: Sun, Jan 1 at 11:00 - Oded Lachish
Niv Buchbinder
Dear all,
Next week we are happy to have Oded Lachish from Centre for Discrete Mathematics and its Applications, University of Warwick.
Note that we moved the seminar to room 8!
You can view the upcoming talks of the seminar at:
See you,
Niv Buchbinder.
%%%%%%%%%%%%%%%%%%%%%%
Computer Science Colloquia - Open University of Israel
%%%%%%%%%%%%%%%%%%%%%%
Time: Sunday, January 1st, at 11:00-12:00
Place: Room 8, Kikar building, Open University.
Speaker: Oded Lachish, Centre for Discrete Mathematics and its Applications, University of Warwick.
-------
Title: Improved Competitive Ratio for the Matroid Secretary Problem
-----
Abstract:
The Matroid Secretary Problem, introduced by Babaioff \textit{et al.} (2007), is a generalization of the Classical Secretary Problem.
In this problem, elements from a matroid are presented to an on-line algorithm in a random order.
Each element has a weight associated with it, which is revealed to the algorithm along with the element.
After each element is revealed the algorithm must make an irrevocable decision on whether or not to select it.
The goal is to pick an independent set with the sum of the weights of the selected elements as large as possible.
Babaioff \textit{et al} gave an algorithm for the Matroid Secretary Problem with a {\it competitive ratio} of $O(log{\rho})$, where $\rho$ is the rank of the matroid.
It has been conjectured that a constant competitive-ratio is achievable for this problem.
This will be about an algorithm that has a competitive-ratio of $O(\sqrt{log{\rho}})$.