Campus Event Calendar
Event Entry
What and Who
Breaking the 3/4 Barrier for Approximate Maximin Share
Hannaneh Akrami
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 21 March 2023
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We study the problem of allocating a set of m indivisible goods among n agents with additive valuations in a fair manner using the popular fairness notion of Maximin share (MMS). Maximin share of agent i (MMS_i) is the maximum value she can guarantee to have assuming that she divides the goods into n bundles and gets the minimum valued bundle. An alpha-MMS allocation is an allocation which gives all agents alpha times their Maximin share. It is known that 1-MMS allocations do not always exist and 3/4-MMS allocations always exist. Yet this factor has not been improved (by an additive constant) since the work of Ghodsi et al. in 2018. We improve the state-of-the-art by showing that (3/4+3/4220)-MMS allocations always exist.
Contact
Roohani Sharma
+49 681 9325 1116
--email hidden
Virtual Meeting Details
Zoom
527 278 8807
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.
Roohani Sharma, 03/20/2023 15:12
Roohani Sharma, 03/04/2023 15:18 -- Created document.
Roohani Sharma, 03/04/2023 15:18 -- Created document.