Numerical semigroups generated by concatenation of arithmetic sequences

Show simple item record

dc.contributor.author Mehta, Ranjana
dc.contributor.author Saha, Joydip
dc.contributor.author Sengupta, Indranath
dc.date.accessioned 2020-05-15T12:42:39Z
dc.date.available 2020-05-15T12:42:39Z
dc.date.issued 2020-03
dc.identifier.citation Mehta, Ranjana; Saha, Joydip and Sengupta, Indranath, "Numerical semigroups generated by concatenation of arithmetic sequences", arXiv, Cornell University Library, DOI: arXiv:1802.02564v7, Mar. 2020. en_US
dc.identifier.uri http://arxiv.org/abs/2004.13933
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/5387
dc.description.abstract The Chamberlin-Courant and Monroe rules are fundamental and well-studied rules in the literature of multi-winner elections. The problem of determining if there exists a committee of size k that has a Chamberlin-Courant (respectively, Monroe) score of at most r is known to be NP-complete. We consider the following natural problems in this setting: a) given a committee S of size k as input, is it an optimal k-sized committee, and b) given a candidate c and a committee size k, does there exist an optimal k-sized committee that contains c? In this work, we resolve the complexity of both problems for the Chamberlin-Courant and Monroe voting rules in the settings of rankings as well as approval ballots. We show that verifying if a given committee is optimal is coNP-complete whilst the latter problem is complete for ?P2. We also demonstrate efficient algorithms for the second problem when the input consists of single-peaked rankings. Our contribution fills an essential gap in the literature for these important multi-winner rules.
dc.description.statementofresponsibility by Chinmay Sonar, Palash Dey and Neeldhara Misra
dc.language.iso en_US en_US
dc.publisher Cornell University Library en_US
dc.title Numerical semigroups generated by concatenation of arithmetic sequences en_US
dc.type Pre-Print en_US
dc.relation.journal arXiv


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