On Efficient Computation of DiRe Committees

• URL: http://arxiv.org/abs/2402.19365v1
• Date: Thu, 29 Feb 2024 17:13:30 GMT
• Title: On Efficient Computation of DiRe Committees
• Authors: Kunal Relia
• Abstract summary: Consider a committee election consisting of a set of candidates who are divided into arbitrary groups each of size emphat most two. A diversity constraint stipulates the selection of emphat least one candidate from each group. A representation constraint stipulates the selection of emphat least one candidate from each population who has a non-null set of approved candidates.
• Score: 4.8951183832371
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Consider a committee election consisting of (i) a set of candidates who are divided into arbitrary groups each of size \emph{at most} two and a diversity constraint that stipulates the selection of \emph{at least} one candidate from each group and (ii) a set of voters who are divided into arbitrary populations each approving \emph{at most} two candidates and a representation constraint that stipulates the selection of \emph{at least} one candidate from each population who has a non-null set of approved candidates. The DiRe (Diverse + Representative) committee feasibility problem (a.k.a. the minimum vertex cover problem on unweighted undirected graphs) concerns the determination of the smallest size committee that satisfies the given constraints. Here, for this problem, we discover an unconditional deterministic polynomial-time algorithm that is an amalgamation of maximum matching, breadth-first search, maximal matching, and local minimization.

Related papers

• Computing Voting Rules with Elicited Incomplete Votes [11.550634521005968]
  We study voting rules that are computable by querying voters about $t m$ candidates. For scoring rules that are computable with limited-sized queries, we give parameterized upper and lower bounds on the number of such queries.
  arXiv  Detail & Related papers  (2024-02-16T22:17:01Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Concomitant Group Testing [49.50984893039441]
  We introduce a variation of the group testing problem capturing the idea that a positive test requires a combination of multiple types'' of item. The goal is to reliably identify all of the semi-defective sets using as few tests as possible. Our algorithms are distinguished by (i) whether they are deterministic (zero-error) or randomized (small-error), and (ii) whether they are non-adaptive, fully adaptive, or have limited adaptivity.
  arXiv  Detail & Related papers  (2023-09-08T09:11:12Z)
• On the Complexity of Finding a Diverse and Representative Committee using a Monotone, Separable Positional Multiwinner Voting Rule [0.0]
  A growing line of research in computational social choice concerns the use of constraints to ensure fairness in elections. Recent work proposed a model to find a diverse emphand representative committee and studied the model's computational aspects. Here, we classify the complexity of finding a diverse and representative committee using a monotone, separable positional multiwinner voting rule.
  arXiv  Detail & Related papers  (2022-11-23T18:56:44Z)
• A Nested Genetic Algorithm for Explaining Classification Data Sets with Decision Rules [3.8271082752302137]
  We aim to automatically extract a set of decision rules (rule set) that best explains a classification data set. First, a large set of decision rules is extracted from a set of decision trees trained on the data set. The rule set should be concise, accurate, have a maximum coverage and minimum number of inconsistencies.
  arXiv  Detail & Related papers  (2022-08-23T11:42:15Z)
• Leximax Approximations and Representative Cohort Selection [10.55182802721649]
  Finding a representative cohort from a broad pool of candidates is a goal that arises in many contexts. Finding a leximax solution can be highly dependent on small variations in the utility of certain groups. We show that finding an integer solution to leximax cohort selection with linear utilities is NP-Hard.
  arXiv  Detail & Related papers  (2022-05-02T18:43:25Z)
• Uniformity in Heterogeneity:Diving Deep into Count Interval Partition for Crowd Counting [56.44300325295678]
  We propose a novel count interval partition criterion called Uniform Error Partition (UEP) MCP criterion selects the best count proxy for each interval to represent its count value during inference. We propose a simple yet effective model termed Uniform Error Partition Network (UEPNet)
  arXiv  Detail & Related papers  (2021-07-27T06:24:15Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV) In general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee.
  arXiv  Detail & Related papers  (2021-04-19T08:26:40Z)
• Representative Committees of Peers [21.26271260313741]
  We show that a k-sortition leads to an outcome within the factor 1+O (1/k) of the optimal social cost for any number of voters. For large issues, we demonstrate that the k-sortition is the worst-case optimal rule within a broad family of committee-based rules.
  arXiv  Detail & Related papers  (2020-06-14T08:20:47Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.