Setareh Taki

2 accepted papers

2023

Simplification and Improvement of MMS Approximation

Hannaneh Akrami, Jugal Garg, Eklavya Sharma, Setareh Taki

IJCAI 2023poster

We consider the problem of fairly allocating a set of indivisible goods among n agents with additive valuations, using the popular fairness notion of maximin share (MMS). Since MMS allocations do not always exist, a series of works provided existence and algorithms for approximate MMS allocations. T…

Cited by 25 Source ↗PDF ↗Scholar ↗

2021

On the PTAS for Maximin Shares in an Indivisible Mixed Manna

Rucha Kulkarni, Ruta Mehta, Setareh Taki

AAAI 2021technical

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 re…

Cited by 6 Source ↗PDF ↗Scholar ↗