Parameterized Complexity of Envy-Free Resource Allocation in Social Networks
Authors: Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak7135-7142
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We initiate the study of the parameterized complexity of these resource allocation problems by considering natural parameters which capture structural properties of the network and similarities between agents and items. In particular, we show that even very general fragments of the considered problems become tractable as long as the social network has bounded treewidth or bounded clique-width. We complement our results with matching lower bounds which show that our algorithms cannot be substantially improved. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Royal Holloway, University of London, UK. Email: eduard.eiben@rhul.ac.uk 2Algorithms and Complexity Group, TU Wien, Austria. Emails: rganian@gmail.com, thamm@ac.tuwien.ac.at 3Department of Computer Science, The University of Sheffield, UK. Email: sordyniak@gmail.com |
| Pseudocode | No | The paper describes algorithms (e.g., dynamic programming approach, integer linear program setup) but does not provide structured pseudocode blocks or formally labeled algorithm listings. |
| Open Source Code | No | The paper does not provide any statement or link regarding the public availability of source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper focused on complexity, algorithms, and lower bounds. It does not use or refer to any datasets in an empirical sense that would require public access information. |
| Dataset Splits | No | This is a theoretical paper and does not describe empirical experiments using dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper and does not describe empirical experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and complexity. While it mentions concepts like Integer Linear Programming, it does not specify any software dependencies with version numbers for reproducing its theoretical findings or any empirical results. |
| Experiment Setup | No | This is a theoretical paper and does not describe empirical experiments with specific setup details like hyperparameters or training configurations. |