Can I read How to assign volunteers to tasks compatibly ? A graph theoretic and parameterized approach on EtoBox?

How to assign volunteers to tasks compatibly ? A graph theoretic and parameterized approach by Gupta, Sushmita; Jain, Pallavi; Saurabh, Saket is a scholarly article available to read on EtoBox.

What is How to assign volunteers to tasks compatibly ? A graph theoretic and parameterized approach about?

In this paper we study a resource allocation problem that encodes correlation between items in terms of \conflict and maximizes the minimum utility of the agents under a conflict free allocation. Admittedly, the problem is computationally hard even under stringent restrictions because it encodes a variant of the {\sc Maximum Weight Independent Set} problem which is one of the canonical hard problems in both classical and parameterized complexity. Recently, this subject was explored by Chiarelli et al.~[Algorithmica'22] from the classical complexity perspective to draw the boundary between {\sf NP}-hardness and tractability for a constant number of agents. The problem was shown to be hard even for small constant number of agents and various other restrictions on the underlying graph. Notwithstanding this computational barrier, we notice that there are several parameters that are worth studying: number of agents, number of items, combinatorial structure that defines the conflict among the items, all of which could well be small under specific circumstancs. Our search rules out several parameters (even when taken together) and takes us towards a characterization of families of input i

Author

Gupta, Sushmita; Jain, Pallavi; Saurabh, Saket

Published

2023

Language

EN