More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules
Authors: Sushmita Gupta, Pallavi Jain, Souvik Saha, Saket Saurabh, Anannya Upasana
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | With respect to this parameter, we design parameterized approximation schemes, a lossy polynomial-time preprocessing method, and show that an extra committee member suffices to achieve the desired score (i.e., 1-additive approximation). Additionally, we resolve an open question by Yang and Wang regarding the fixed-parameter tractability of the problem under the PAV rule with the total score as the parameter, demonstrating that it admits an FPT algorithm. We will design and run two different algorithms for two possible cases, based on the value of t (we call it threshold). A brief description of FPT-AS that combines both cases is given in Algorithm 1. Recall that we defined ̸min = min{̸v 1 | v V}. Let r = 4dk ̸̸min + k. |
| Researcher Affiliation | Academia | Sushmita Gupta1 , Pallavi Jain2 , Souvik Saha1 , Saket Saurabh1, and Anannya Upasana1 1The Institute of Mathematical Sciences, HBNI 2Indian Institute of Technology Jodhpur EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1 Apx-Mw E: An FPT-approximation scheme for SM-MWE. Algorithm 2 Add-Apx-Mw E: An FPT algorithm for one-additive approximation of MAX SUBMOD-MWE. |
| Open Source Code | No | The paper does not provide any explicit statement about the release of source code, a link to a code repository, or mention of code in supplementary materials for the methodology described. |
| Open Datasets | No | The paper describes theoretical algorithms and proofs related to multiwinner election problems and does not mention the use of any specific publicly available datasets for experimental evaluation. |
| Dataset Splits | No | The paper presents theoretical algorithms and does not involve experimental evaluation on datasets, therefore no dataset splits are discussed. |
| Hardware Specification | No | The paper focuses on theoretical algorithms and their complexity, and does not describe any experimental hardware used for empirical evaluation. |
| Software Dependencies | No | The paper describes theoretical algorithms and proofs and does not specify any software dependencies or their versions for implementation or execution. |
| Experiment Setup | No | The paper is theoretical in nature, focusing on algorithm design and proofs, and therefore does not include details about an experimental setup, hyperparameters, or system-level training settings. |