BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260909T041621Z
UID:Seminar-dept-382@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20150520T130000
DTEND:20150520T140000
SUMMARY:School Seminar Series
DESCRIPTION:Prof Vangelis Markakis: Approximation Algorithms for Computing Maximin Share Allocations\n\nWe study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of n agents and a set of goods, the maximin share of a single agent is the best that he can guarantee to himself, if he partitions the goods into n bundles and receives his least desirable bundle. The objective then is to find a partition, so that each player is guaranteed his maximin share. \n\nIn the presence of indivisible goods, such allocations are not guaranteed to exist, hence, we resort to approximation algorithms. \n\nOur main result is a 2/3-approximation algorithm, which runs in polynomial time for any number of agents and goods, improving upon previous results in the literature. We also investigate some special cases and provide better approximation guarantees. Finally, we provide a probabilistic analysis, showing that maximin share allocations exist in most cases (i.e., with probability 1-o(1) on randomly generated instances). This is in accordance with the apparent difficulty reported in previous works, for obtaining impossibility results.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=382
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR