Can I read FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares on EtoBox?

FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares by Jansen, Klaus; Lassota, Alexandra; Tutas, Malte; Vetta, Adrian is a scholarly article available to read on EtoBox.

What is FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares about?

We study the computational complexity of fairly allocating indivisible, mixed-manna items. For basic measures of fairness, this problem is hard in general. Thus, research has flourished concerning input classes where efficient algorithms exist, both for the purpose of establishing theoretical boundaries and for the purpose of designing practical algorithms for real-world instances. Notably, the paradigm of fixed-parameter tractability (FPT) has lead to new insights and improved algorithms for a variety of fair allocation problems; see, for example, Bleim et al. (IJCAI 16), Aziz et al. (AAAI 17), Bredereck et al. (EC 19) and Kulkarni et al. (EC 21). Our focus is the fairness measure maximin shares (MMS). Motivated by the general non-existence of MMS allocations, Aziz et al. (AAAI 17) studied optimal MMS allocations, namely solutions that achieve the best $\alpha$-approximation for the maximin share value of every agent. These allocations are guaranteed to exist, prompting the important open question of whether optimal MMS allocations can be computed efficiently. We answer this question affirmatively by providing FPT algorithms to output optimal MMS allocations. Furthermore, our tech

Author

Jansen, Klaus; Lassota, Alexandra; Tutas, Malte; Vetta, Adrian

Published

2024

Language

EN