Online bipartite matching with imperfect advice
Authors: Davin Choo, Themistoklis Gouleakis, Chun Kai Ling, Arnab Bhattacharyya
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | While our contributions are mostly theoretical, we give and discuss various practical extensions of TESTANDMATCH, and also show preliminary experiments in Appendix F. |
| Researcher Affiliation | Academia | 1School of Computing, National University of Singapore 2Industrial Engineering and Operations Research, Columbia University. |
| Pseudocode | Yes | Algorithm 1 TESTANDMATCH Algorithm 2 MIMIC Algorithm 3 MINIMAXTEST Algorithm 4 SIMULATEP |
| Open Source Code | Yes | The source code is available at https://github.com/cxjdavin/ online-bipartite-matching-with-imperfect-advice. |
| Open Datasets | Yes | Our problem instances are generated from the synthetic hard known IID instance of (Manshadi et al., 2012) where any online algorithm achieves a competitive ratio of at most 0.823 in expectation. |
| Dataset Splits | No | The paper describes a generative process for instances but does not specify explicit train/validation/test splits, percentages, or absolute sample counts for data partitioning. The problem is online, so data arrives sequentially rather than being split into traditional fixed datasets. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., CPU, GPU models, memory, or cloud instance types) used for running the experiments. It only mentions "preliminary experiments." |
| Software Dependencies | No | The paper mentions implementing TESTANDMATCH but does not list specific software dependencies with version numbers (e.g., Python, PyTorch, TensorFlow, or specific solvers). |
| Experiment Setup | Yes | For our testing threshold, we set ε = ˆn/n β so that τ = 2(ˆn/n β) ε = ˆn/n β. We generated 10 random graph instances with n = 2000 offline and n online vertices. Starting with perfect advice ˆc = c , we corrupt the advice by an α parameter using two types of corruption. |