Approximation and Parameterized Complexity of Minimax Approval Voting
Authors: Marek Cygan, Łukasz Kowalik, Arkadiusz Socała, Krzysztof Sornat
JAIR 2018 | Venue PDF | Archive PDF | Plain Text | 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, Nabeel and Singh 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), where n is a number of voters and m is a number of alternatives. |
| Researcher Affiliation | Academia | Marek Cygan EMAIL Lukasz Kowalik EMAIL Arkadiusz Soca la EMAIL Department of Mathematics Informatics and Mechanics University of Warsaw, Poland Krzysztof Sornat EMAIL Department of Mathematics and Computer Science University of Wroc law, Poland |
| Pseudocode | Yes | Pseudocode 1: Parameterized approximation scheme for Minimax Approval Voting. Pseudocode 2: The algorithm from Theorem 5.1 |
| Open Source Code | No | A further algorithm engineering research effort can help to turn our ideas into a useful implementation. |
| Open Datasets | No | The paper is theoretical, analyzing the complexity and proposing approximation schemes for an algorithmic problem. It uses abstract inputs like "multiset S = {s1, . . . , sn} of 0-1 strings" without referencing any specific, named public datasets for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical, focusing on algorithmic complexity and approximation schemes. It does not conduct empirical experiments or use specific datasets that would require train/test/validation splits. |
| Hardware Specification | No | The paper is theoretical, focusing on the complexity and approximation algorithms for Minimax Approval Voting. It does not describe any empirical experiments, and therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical, describing algorithms and their complexity bounds. While it mentions solving a Linear Program (LP) using the "interior point method (Karmarkar, 1984)", it does not specify any particular software, libraries, or their version numbers that were used for an implementation or empirical evaluation. |
| Experiment Setup | No | The paper is theoretical, presenting approximation schemes and complexity results for Minimax Approval Voting. It does not describe any empirical experiments or their setup, thus no hyperparameters or system-level training settings are provided. |