BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20181028T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20180325T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20190331T020000
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.13537.field_data.0@www.diag.uniroma1.it
DTSTAMP:20240521T041830Z
CREATED:20181011T112708Z
DESCRIPTION:We present an optimal\, e-competitive truthful mechanism for th
e weighted bipartite matching problem. We consider its online version whe
re the first vertex set is known beforehand\, but vertices of the second
set appear one after another in random order (secretary model). Vertices o
f the first set are interpreted as items\, and those of the second set as
bidders. On arrival\, each bidder vertex reveals the weights of all adjace
nt edges and the algorithm has to decide which of those to add to the matc
hing.It has been shown that the upper and lower bound of e for the origina
l secretary problem extends to various other problems even with rich combi
natorial structure\, one of them being weighted bipartite matching. But tr
uthful mechanisms so far fall short of reasonable competitive ratios once
respective algorithms deviate from the original\, simple threshold form. T
he best known mechanism for weighted bipartite matching offers only a rati
o logarithmic in the number of online vertices. We close this gap\, showin
g that truthfulness does not impose any additional bounds.
DTSTART;TZID=Europe/Paris:20181012T140000
DTEND;TZID=Europe/Paris:20181012T140000
LAST-MODIFIED:20191008T082735Z
LOCATION:Aula Magna DIAG\, via Ariosto 25
SUMMARY:An Optimal Truthful Mechanism for the Online Weighted Bipartite Mat
ching Problem - Rebecca Reiffenhauser (RWTH Aachen)
URL;TYPE=URI:https://www.diag.uniroma1.it/node/13537
END:VEVENT
END:VCALENDAR