BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20240331T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20231029T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260425T090753Z
UID:651a7768aefdb351705414@ist.ac.at
DTSTART:20231207T110000
DTEND:20231207T121500
DESCRIPTION:Speaker: Ivan Sergeev\nAbstract: The matroid secretary problem 
 (MSP) is an online selection problem where elements of a weighted matroid 
 are revealed one by one\, and the goal is to pick an independent set of as
  large weight as possible. This setting is motivated by applications in on
 line mechanism design and generalizes the classical secretary problem. It 
 was conjectured that\, similar to the classical secretary\, there exists a
 n algorithm that is constant-competitive for any matroid. Despite the long
  line of work dedicated to the problem\, so far constant competitive ratio
  has been attained only for certain classes of matroids and for some varia
 tions of MSP. One example is the random assignment model (RAMSP)\, where a
 n adversary fixes a number of weights equal to the cardinality of the matr
 oid\, which then get randomly assigned to the elements of the ground set. 
 However\, the two known constant-competitive algorithms for this setting\,
  one by Soto (2013) and the other by Oveis Gharan and Vondrák (2013)\, cr
 ucially rely on knowing the full matroid upfront. Lifting this requirement
  was left as an open question by the aforementioned authors\, as there are
  good arguments for why such assumptions on prior information should be av
 oided. In this talk\, I will present a constant-competitive algorithm for 
 RAMSP that only needs to know the cardinality of the underlying matroid up
 front\, making RAMSP the first known MSP variant admitting such an algorit
 hm.
LOCATION:Moonstone Bldg / Ground floor / Seminar Room C (I24.EG.030c)\, IST
 A
ORGANIZER:dsaulpic@ist.ac.at
SUMMARY:Ivan Sergeev: Matroid secretary problem with random assignment and 
 almost no prior information 
URL:https://talks-calendar.ista.ac.at/events/4625
END:VEVENT
END:VCALENDAR