Tight Approximation for Proportional Approval Voting
Authors: Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, Krzysztof Sornat
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result (Theorem 1) is a tight αw-approximation algorithm for a natural class of geometrically dominant w-THIELE rules, where αw is a sequence-dependent constant defined in (1). Resulting approximation ratios for selected w-THIELE rules are presented in Table 1. The algorithm is relatively simple: first we solve a linear program and then we round a solution by employing a framework called pipage rounding due to Ageev and Sviridenko (2004) and Calinescu et al. (2011). We provide a matching lower bound via a reduction from the Label Cover problem. Moreover, assuming a conjecture called Gap-ETH, we show that better approximation ratio cannot be obtained even in time f(k)*pow(n,o(k)). |
| Researcher Affiliation | Collaboration | Szymon Dudycz1 , Pasin Manurangsi2 , Jan Marcinkowski1 and Krzysztof Sornat1,3 1University of Wrocław, Poland 2Google Research, US 3Ben-Gurion University, Israel szymon.dudycz@cs.uni.wroc.pl, pasin@google.com, {jan.marcinkowski, krzysztof.sornat}@cs.uni.wroc.pl |
| Pseudocode | No | The paper describes the algorithm in prose, stating: "Our algorithm is based on an LP rounding technique, which requires us to first define scr E w also on a fractional solution x [0, 1]C specifying for each candidate fractionally, how much the candidate is selected." It does not include a structured pseudocode block or an algorithm box. |
| Open Source Code | No | The paper does not contain any statement about making its source code available, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper is theoretical, focusing on algorithm design, proofs, and hardness results. It does not involve empirical evaluation on datasets, and thus no public dataset information is provided. |
| Dataset Splits | No | The paper is theoretical and does not perform empirical evaluations. Therefore, it does not discuss validation splits for datasets. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and complexity analysis. It does not mention any hardware specifications used for computation or experimentation. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and complexity analysis. It does not mention any specific software dependencies or their version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any empirical experimental setup, hyperparameters, or training settings for a model. |