(Optimal) Online Bipartite Matching with Degree Information
Authors: Anders Aamand, Justin Chen, Piotr Indyk
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments We complement our theoretical studies with an extensive empirical evaluation of MPD for multiple random graph models and real graph benchmarks in Section 7. |
| Researcher Affiliation | Academia | Anders Aamand MIT aamand@mit.edu Justin Y. Chen MIT justc@mit.edu Piotr Indyk MIT indyk@mit.edu |
| Pseudocode | Yes | Algorithm 1 Min Predicted Degree |
| Open Source Code | Yes | Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] See supplementary material. |
| Open Datasets | Yes | Oregon: 9 graphs sampled over 3 months representing a communication network of internet routers from the Stanford SNAP Repository [37]. |
| Dataset Splits | No | The paper describes running experiments over 100 trials with randomized online node arrival order but does not specify explicit train/validation/test dataset splits with percentages or counts. |
| Hardware Specification | Yes | The experiments were all run on a 2018 Mac Book Pro. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers. |
| Experiment Setup | Yes | In our experiments, we set size n = m = 1000, set C = m/2, and vary the exponent . and For MPD, the offline degree predictor σ : U ! R is based on the first graph: if an offline node u (i.e. a specific router) appeared in the first graph, σ(u) is the degree of u in that graph. If an offline node u did not appear in the first graph, σ(u) = 1. |