Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers

Show simple item record

dc.contributor.author Dey, Palash
dc.contributor.author Misra, Neeldhara
dc.contributor.author Narahari, Y.
dc.date.accessioned 2019-04-24T06:26:17Z
dc.date.available 2019-04-24T06:26:17Z
dc.date.issued 2019-04
dc.identifier.citation Dey, Palash; Misra, Neeldhara and Narahari, Y., "Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers", Theoretical Computer Science, DOI: 10.1016/j.tcs.2019.03.022, Apr. 2019. en_US
dc.identifier.uri https://doi.org/10.1016/j.tcs.2019.03.022
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/4391
dc.description.abstract Approval voting provides an opportunity for the agents to make a comment about every candidate, without incurring the overhead of determining a full ranking on the entire set of candidates. This makes approval voting a natural choice for many practical applications. In this work, we focus on the use of approval voting for selecting a committee in scenarios where we can have few outrageous voters whom we call outliers. More specifically, we study the computational complexity of the committee selection problem for commonly used approval-based voting rules in the presence of outliers. Our first result shows that outliers render the committee selection problem intractable for approval, net approval, and minisum approval voting rules. We next study the parameterized complexity of this problem with five natural parameters, namely the target score, the size of the committee (and its dual parameter namely the number of candidates outside the committee); and the number of outliers (and its dual parameter namely the number of non-outliers). Our main contribution in this paper is dichotomous results, which establish the parameterized complexity of the problem of selecting a committee under approval, net approval, and minisum approval voting rules for all subsets of the above five parameters considered here (by showing either FPT or W[1] -hardness for all subsets of parameters).
dc.description.statementofresponsibility by Palash Dey, Neeldhara Misra and Y Narahari
dc.language.iso en en_US
dc.publisher Elsevier en_US
dc.subject Voting en_US
dc.subject Approval ballot en_US
dc.subject Committee selection en_US
dc.subject Outliers en_US
dc.subject Parameterized complexity en_US
dc.subject Parameterized dichotomy en_US
dc.title Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers en_US
dc.type Article en_US
dc.relation.journal Theoretical Computer Science


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account