Numerical semigroups generated by concatenation of arithmetic sequences

Show simple item record Mehta, Ranjana Saha, Joydip Sengupta, Indranath 2020-05-15T12:42:39Z 2020-05-15T12:42:39Z 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.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


My Account