On the Online Coalition Structure Generation Problem
Authors: Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Mordechai Shalom, Shmuel Zaks
JAIR 2021 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show tight or nearly tight bounds for the competitive ratio in each case. Our main technical results are the Ω(log2 W) lower bound (Thm. 4.5) for the competitive ratio of Maximum Fractional Weight Coalition Structure Generation with positive weights, and the matching upper bound (Thm. 4.4)... |
| Researcher Affiliation | Academia | Michele Flammini EMAIL GSSI, L Aquila, Italy Gianpiero Monaco EMAIL University of L Aquila, Italy Luca Moscardelli EMAIL University of Chieti-Pescara, Italy Mordechai Shalom EMAIL Isik University, Istanbul, Turkey Shmuel Zaks EMAIL Technion, Haifa, Israel |
| Pseudocode | Yes | Algorithm 1 Greedy Initialization: ... Algorithm 2 Greedyα Initialization: ... Algorithm 3 Maximal Matching Initialization: ... Algorithm 4 Classify Initialization: |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. It mentions a preliminary version in conference proceedings but not a code release. |
| Open Datasets | No | The paper analyzes a theoretical problem on 'an undirected edge-weighted graph (V, E, w)' and does not mention specific publicly available datasets used for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation on datasets, thus no dataset splits are mentioned. |
| Hardware Specification | No | The paper does not provide specific hardware details, as it focuses on theoretical analysis and algorithm design rather than empirical experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers, as it presents theoretical results and algorithms. |
| Experiment Setup | No | The paper does not provide specific experimental setup details such as hyperparameters or training configurations, as it is a theoretical work. |