Related papers: On Efficient Computation of DiRe Committees

Related papers

Precedence-Constrained Decision Trees and Coverings [0.8594140167290095]
This work considers a number of optimization problems and reductive relations between them.<n>The two main problems we are interested in are the emph Optimal Decision Tree and emphSet Cover.
arXiv Detail & Related papers (2026-02-24T19:33:36Z)
Efficient Algorithms for Electing Successive Committees [9.083041508439509]
In a recently introduced model of successive committee elections, one aims to find a sequence of a given length of "best" same-size committees.<n>However, the described task turns out to be NP-hard for most selection criteria already for seeking committees of size three.<n>We devise algorithms that effectively solve the mentioned hard cases in realistic scenarios of a moderate number of candidates or of a limited time horizon.
arXiv Detail & Related papers (2025-05-23T18:32:14Z)
Speeding up Local Search for the Indicator-based Subset Selection Problem by a Candidate List Strategy [0.0]
In evolutionary multi-objective optimization, the indicator-based subset selection problem involves finding a subset of points that maximizes a given quality indicator. Local search is an effective approach for obtaining a high-quality subset in this problem. This paper proposes a candidate list strategy for local search in the indicator-based subset selection problem.
arXiv Detail & Related papers (2025-03-06T09:06:49Z)
Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
We improve the approximation factor of the fastest deterministic algorithm from $6+epsilon$ to $5+epsilon$. Our technique is based on optimizing the performance of two components: the threshold greedy subroutine and the building of two disjoint sets as candidate solutions.
arXiv Detail & Related papers (2024-05-20T02:24:58Z)
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)
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z)
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)
Best Policy Identification in Linear MDPs [70.57916977441262]
We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
arXiv Detail & Related papers (2022-08-11T04:12:50Z)
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)
Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
We study the algorithmic task of finding a large independent set in a sparse ErdHos-R'enyi random graph. We show that the class of low-degree algorithms can find independent sets of half-optimal size but no larger.
arXiv Detail & Related papers (2020-10-13T17:26:09Z)
Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time [16.346069386394703]
We consider the problem of monotone, submodular over a ground set of size $n$ subject to cardinality constraint $k$. We introduce the first deterministic algorithms with linear time complexity; these algorithms are streaming algorithms. Our single-pass algorithm obtains a constant ratio in $lceil n / c rceil + c$ oracle queries, for any $c ge 1$.
arXiv Detail & Related papers (2020-09-10T16:35:54Z)
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.