Efficient Algorithms for Electing Successive Committees
In a recently introduced model of successive committee elections (Bredereck et al., AAAI-20) for a given set of ordinal or approval preferences one aims to find a sequence of a given length of "best" same-size committees such that each candidate is a member of a limited number of consecutive committees. However, the practical usability of this model remains limited, as the described task turns out to be NP-hard for most selection criteria already for seeking committees of size three. Non-trivial or somewhat efficient algorithms for these cases are lacking too. Motivated by a desire to unlock the full potential of the described temporal model of committee elections, we devise (parameterized) algorithms that effectively solve the mentioned hard cases in realistic scenarios of a moderate number of candidates or of a limited time horizon.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
No-Regret Forecasting with Egalitarian Committees
The forecast combination puzzle is often found in literature: The equal-weight scheme tends to outperform sophisticated methods of combining individual forecasts. Exploiting this finding, we propose a hedge egalitarian c…
regressionHybrid Learning with New Value Function for the Maximum Common Subgraph Problem
Maximum Common induced Subgraph (MCS) is an important NP-hard problem with wide real-world applications. Branch-and-Bound (BnB) is the basis of a class of efficient algorithms for MCS, consisting in successively selectin…
Reinforcement Learning (RL)A characterization of proportionally representative committees
A well-known axiom for proportional representation is Proportionality of Solid Coalitions (PSC). We characterize committees satisfying PSC as possible outcomes of the Minimal Demand rule, which generalizes an approach pi…
A Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem
We present a graph neural network assisted Monte Carlo Tree Search approach for the classical traveling salesman problem (TSP). We adopt a greedy algorithm framework to construct the optimal solution to TSP by adding the…
Graph Neural NetworkTraveling Salesman ProblemConvolutional Neural Network Committees for Melanoma Classification with Classical And Expert Knowledge Based Image Transforms Data Augmentation
Skin cancer is a major public health problem, as is the most common type of cancer and represents more than half of cancer diagnoses worldwide. Early detection influences the outcome of the disease and motivates our work…
Data AugmentationGeneral Classification