BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY: Algorithms for the Matroid Secretary Problem
DTSTART:20140617T163000
DTSTAMP:20260406T103735Z
UID:9a83fac301746449801e43c45d4106b302d4f11ad04db3540c0829de
CATEGORIES:Conferences - Seminars
DESCRIPTION:Ola SVENSSON\, EPFL\nThe last decade has seen an increased int
 erest in generalizations of the secretary problem\, a classical online pro
 blem. These generalizations have numerous applications in mechanism design
  for settings involving the selling of a good (e.g. ad) to agents (eg. pag
 e\nviews) arriving online. One\nof the most well-studied variants is calle
 d the matroid secretary problem. The matroid secretary problem is general 
 enough to deal with complex settings and\, at the same time\, it is suffic
 iently restricted to admit good algorithms. A famous conjecture states tha
 t there is in fact an online algorithm that performs almost as well as any
  offline algorithm with perfect information.\nIn this talk\, we discuss al
 gorithms 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 al
 gorithm 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 a
 t most a O(log log n) factor by making our decisions online compared to se
 lecting an optimal solution calculated offline.\nThis is joint work with M
 oran Feldman (EPFL) and Rico Zenklusen (ETHZ).
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR