Approximation and Hardness of Shift-Bribery
Authors: Piotr Faliszewski, Pasin Manurangsi, Krzysztof Sornat1901-1908
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide approximation algorithms and inapproximability results for the SHIFT-BRIBERY problem... Our main contribution is the first polynomial-time approximation scheme (PTAS)... For the case of the Copeland rule, we give a reduction that preserves approximation ratios... We omit some of the proofs due to space restrictions, but all of them are available upon request. |
| Researcher Affiliation | Academia | Piotr Faliszewski AGH University Krakow, Poland faliszew@agh.edu.pl Pasin Manurangsi UC Berkeley, USA pasin@berkeley.edu Krzysztof Sornat University of Wrocław, Poland and IDSIA, USI-SUPSI, Switzerland krzysztof.sornat@cs.uni.wroc.pl |
| Pseudocode | No | The paper describes algorithms in prose and presents linear programming formulations (Figure 1, 2, 3), but it does not include explicit pseudocode blocks or clearly labeled algorithm sections. |
| Open Source Code | No | The paper does not provide any statement or link indicating the release of open-source code for the described methodology. |
| Open Datasets | No | The paper focuses on theoretical proofs and algorithms, not empirical experiments. Therefore, no datasets or access information for them are provided. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments. Thus, there is no mention of training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments requiring specific software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical algorithms and proofs, not empirical experiments. Therefore, no experimental setup details like hyperparameters or training settings are provided. |