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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
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. |