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:20240419T113842Z
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