Voting-Based Group Formation
Authors: Piotr Faliszewski, Arkadii Slinko, Nimrod Talmon
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the computational complexity of this problem (and several of its variants) for Approval elections. Our main findings are as follows: 1. If either the number of agents or the number of potential group leaders is small, then the problem can be solved efficiently (formally speaking, the problem is in FPT for the parameterizations by the number of agents or the number of potential group leaders). 2. For the case of partitioning the agents into two groups, the problem is in P if either each agent approves at most two group leaders, or each agent approves almost all group leaders with the exception of one or two. 3. The problem becomes NP-hard as soon as each agent approves up to six group leaders (even for two groups). |
| Researcher Affiliation | Academia | Piotr Faliszewski AGH University Krakow, Poland faliszew@agh.edu.pl Arkadii Slinko University of Auckland Auckland, New Zealand a.slinko@auckland.ac.nz Nimrod Talmon Weizmann Institute Rehovot, Israel nimrodtalmon77@gmail.com |
| Pseudocode | No | The paper describes algorithms in prose and mathematical notation but does not include formal pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | This paper is theoretical research and does not use or mention any datasets for training. |
| Dataset Splits | No | This paper is theoretical research and does not involve dataset splits for validation. |
| Hardware Specification | No | This paper is theoretical research and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical research and does not describe an experimental setup or hyperparameters. |