Generalized Stochastic Matching
Authors: Alireza Farhadi, Jacob Gilbert, MohammadTaghi Hajiaghayi10008-10015
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We will discuss the first algorithms and analysis for this generalization of the stochastic matching model and prove that they achieve good approximation ratios. In particular, we show that the approximation factor of a natural algorithm for this problem is at least 0.6568 in unweighted graphs, and 1/2 + ϵ in weighted graphs for some constant ϵ > 0. We further improve our result for unweighted graphs to 2/3 using edge degree constrained subgraphs (EDCS). |
| Researcher Affiliation | Academia | Alireza Farhadi, Jacob Gilbert, Mohammad Taghi Hajiaghayi University of Maryland |
| Pseudocode | Yes | Algorithm 1: An algorithm for the generalized stochastic matching problem. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the described methodology. |
| Open Datasets | No | The paper discusses theoretical algorithms and their analysis; it does not present new experimental results that would require a publicly available training dataset. While it mentions prior work used "simulated and real data from the United Network for Organ Sharing", this paper's contribution is theoretical. |
| Dataset Splits | No | The paper is theoretical in nature and does not describe an experimental setup with dataset splits (training, validation, test). |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers required for reproducing practical experiments. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis. It does not provide experimental setup details such as hyperparameters or system-level training settings. |