Algorithms for the Matroid Secretary Problem
Event details
| Date | 17.06.2014 |
| Hour | 16:30 |
| Speaker | Ola SVENSSON, EPFL |
| Location | |
| Category | Conferences - Seminars |
The last decade has seen an increased interest in generalizations of the secretary problem, a classical online problem. These generalizations have numerous applications in mechanism design for settings involving the selling of a good (e.g. ad) to agents (eg. page
views) arriving online. One
of the most well-studied variants is called the matroid secretary problem. The matroid secretary problem is general enough to deal with complex settings and, at the same time, it is sufficiently restricted to admit good algorithms. A famous conjecture states that there is in fact an online algorithm that performs almost as well as any offline algorithm with perfect information.
In this talk, we discuss algorithms that make progress on this conjecture. In particular, we present a new algorithm that improves on the previously best algorithm, both in terms of its competitive ratio and its simplicity. The main idea of our algorithm is to decompose the problem into a distribution over a simple type of matroid secretary problems which are easy to solve. We show that this leads to a O(log log n)-competitive algorithm, which means that we lose at most a O(log log n) factor by making our decisions online compared to selecting an optimal solution calculated offline.
This is joint work with Moran Feldman (EPFL) and Rico Zenklusen (ETHZ).
views) arriving online. One
of the most well-studied variants is called the matroid secretary problem. The matroid secretary problem is general enough to deal with complex settings and, at the same time, it is sufficiently restricted to admit good algorithms. A famous conjecture states that there is in fact an online algorithm that performs almost as well as any offline algorithm with perfect information.
In this talk, we discuss algorithms that make progress on this conjecture. In particular, we present a new algorithm that improves on the previously best algorithm, both in terms of its competitive ratio and its simplicity. The main idea of our algorithm is to decompose the problem into a distribution over a simple type of matroid secretary problems which are easy to solve. We show that this leads to a O(log log n)-competitive algorithm, which means that we lose at most a O(log log n) factor by making our decisions online compared to selecting an optimal solution calculated offline.
This is joint work with Moran Feldman (EPFL) and Rico Zenklusen (ETHZ).
Links
Practical information
- General public
- Free
Organizer
- Boi Faltings
Contact
- Sylvie Thomet