Election with Bribed Voter Uncertainty: Hardness and Approximation Algorithm
Authors: Lin Chen, Lei Xu, Shouhuai Xu, Zhimin Gao, Weidong Shi2572-2579
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | As a first step towards ultimately understanding and addressing this important problem, we show that it does not admit any multiplicative O(1)-approximation algorithm modulo standard complexity assumptions. We further show that there is an approximation algorithm that returns a solution with an additive-ε error in FPT time for any fixed ε. |
| Researcher Affiliation | Collaboration | Lin Chen,1 Lei Xu,2 Shouhuai Xu,3 Zhimin Gao,1 Weidong Shi1 1Department of Computer Science, University of Houston, TX, USA 2Conduent Labs, NC, USA 3Department of Computer Science, University of Texas at San Antonio, TX, USA |
| Pseudocode | No | The paper describes algorithms (e.g., 'we present an approximation algorithm', 'dynamic programming algorithm') but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the described methodology. It does not mention any repository links or explicit code release statements. |
| Open Datasets | No | This paper is theoretical and does not involve empirical evaluation on datasets. Therefore, no information about publicly available datasets or training data is provided. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical evaluation, thus there is no discussion of training/validation/test dataset splits. |
| Hardware Specification | No | This paper is theoretical and does not describe empirical experiments. Therefore, no specific hardware details used for running experiments are provided. |
| Software Dependencies | No | This paper is theoretical and does not describe empirical experiments. Therefore, no specific ancillary software details or version numbers are provided. |
| Experiment Setup | No | This paper is theoretical and does not describe empirical experiments. Thus, no specific experimental setup details, hyperparameters, or training configurations are provided. |