02/02/2021

On the PTAS for Maximin Shares in an Indivisible Mixed Manna

Rucha Kulkarni, Ruta Mehta, Setareh Taki

Keywords:

Abstract Paper Similar Papers

Abstract: We study fair allocation of indivisible items, both goods and chores, under the popular fairness notion of maximin share (MMS). The problem is well-studied when there are only goods (or chores), where a PTAS to compute the MMS values of agents is well-known. In contrast, for the mixed manna, a recent result showed that finding even an approximate MMS value of an agent up to any approximation factor in (0,1] is NP-hard for general instances. In this paper, we complement the hardness result by obtaining a PTAS to compute the MMS value when its absolute value is at least 1/p times either the total value of all the goods or total cost of all the chores, for some constant p valued at least 1.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948917
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 15:40 
 0
 0
 0
 0
 20:02 
 0
 0
 0
 0
 14:56 
 0
 0
 0
 0
 15:26 
 0
 0
 0
 0
 17:39 
 0
 0
 0
 0
 19:32 
 0
 0
 0
 0
 17:06 
 0
 0
 0
 0
 14:42 
 0
 0
 0
 0
 24:42 
 0
 0
 0
 0
 14:22 
 0
 0
 0
 0
 16:43 
 0
 0
 0
 0
 18:01 
 0
 0
 0
 0
 13:34 
 0
 0
 0
 0
 13:41 
 0
 0
 0
 0
 4:20 
 0
 0
 0
 0
 14:57 
 0
 0
 0
 0
 15:12 
 0
 0
 0
 0
 3:12 
 0
 0
 0
 0
 14:28 
 0
 0
 0
 0
 3:05 
 0
 0
 0
 0
 9:07 
 0
 0
 0
 0
 2:50 
 0
 0
 0
 0
 19:40 
 0
 0
 0
 0
 14:16 
 0
 0
 0
 0
 13:41 
 0
 0
 0
 0
 9:20 
 0
 0
 0
 0
 14:47 
 0
 0
 0
 0
 18:46 
 0
 0
 0
 0
 15:03 
 0
 0
 0
 0
 14:50 
 0
 0
 0
 0
 15:42 
 0
 0
 0
 0
 18:31 
 0
 0
 0
 0
 14:24 
 0
 0
 0
 0
 18:15 
 0
 0
 0
 0
 14:39 
 0
 0
 0
 0
 13:37 
 0
 0
 0
 0
 17:06 
 0
 0
 0
 0
 5:00 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 3:07