Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Approximation and Parameterized Complexity of Minimax Approval Voting
Authors: Marek Cygan, _ukasz Kowalik, Arkadiusz Soca_a, Krzysztof Sornat
AAAI 2017 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present three results on the complexity of MINIMAX APPROVAL VOTING. First, we study MINIMAX APPROVAL VOTING parameterized by the Hamming distance d from the solution to the votes. We show MINIMAX APPROVAL VOTING admits no algorithm running in time O (2o(d log d)), unless the Exponential Time Hypothesis (ETH) fails. This means that the O (d2d) algorithm of Misra et al. [AAMAS 2015] is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O ((3/ϵ)2d), which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for MINIMAX APPROVAL VOTING, which runs in time n O(1/ϵ2 log(1/ϵ)) poly(m), almost matching the running time of the fastest known PTAS for CLOSEST STRING due to Ma and Sun [SIAM J. Comp. 2009]. |
| Researcher Affiliation | Academia | Marek Cygan University of Warsaw, Poland EMAIL Łukasz Kowalik University of Warsaw, Poland EMAIL Arkadiusz Socała University of Warsaw, Poland EMAIL Krzysztof Sornat University of Wrocław, Poland EMAIL |
| Pseudocode | Yes | Pseudocode 1: Parameterized approximation scheme for MINIMAX APPROVAL VOTING. |
| Open Source Code | No | The paper does not provide any statements about releasing source code for the described methodology or links to code repositories. |
| Open Datasets | No | This is a theoretical paper focusing on complexity and algorithm design; it does not involve empirical experiments with datasets. |
| Dataset Splits | No | This is a theoretical paper focusing on complexity and algorithm design; it does not involve empirical experiments with dataset splits. |
| Hardware Specification | No | This is a theoretical paper focusing on complexity and algorithm design; it does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | This is a theoretical paper focusing on complexity and algorithm design; it does not list specific software dependencies with version numbers for reproducibility. |
| Experiment Setup | No | This is a theoretical paper focusing on complexity and algorithm design; it does not describe an experimental setup with hyperparameters or training settings. |