Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Learning-Augmented Online Bipartite Fractional Matching
Authors: XianJun Davin Choo, Billy Jin, Yongho Shin
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We empirically validate our algorithms through experiments on synthetic and real-world data. |
| Researcher Affiliation | Academia | Davin Choo Harvard John A. Paulson School Of Engineering And Applied Sciences Harvard University Boston, Massachusetts, USA EMAIL Billy Jin Daniels School of Business Purdue University West Lafayette, Indiana, USA EMAIL Yongho Shin Institute of Computer Science University of Wrocław Wrocław, Poland EMAIL |
| Pseudocode | Yes | Detailed pseudocode is given in Appendix A and a full analysis is provided in the supplementary material. Algorithm 1: Learning-Augmented Balance Algorithm (LAB) Algorithm 2: Push-and-Waterfill Algorithm (PAW) |
| Open Source Code | Yes | Full proofs, further related work, and code are provided in the supplementary material. Source code implementations and experimental scripts are given in the supplementary material. |
| Open Datasets | Yes | We experimented on two families of synthetic graphs Erd os-Rényi (ER) and Upper Triangular (UT), and 6 real-world graphs from the Network Data Repository [RA15]. |
| Dataset Splits | No | We experimented on two families of synthetic graphs Erd os-Rényi (ER) and Upper Triangular (UT), and 6 real-world graphs from the Network Data Repository [RA15]. For n {100, 200, 300} and edge probability p {0.1, 0.2, 0.5}, ER(n, p) graphs are generated with n offline and n online vertices, with each possible bipartite edge existing independently with probability p. For n {100, 200, 300}, each UT(n) graph consists of n offline vertices and n online vertices, where the i-th online vertex is connected to the last n i + 1 offline vertices. Meanwhile, we pre-process6 real-world graphs in a similar manner to [BKP20] to obtain random bipartite graphs: first, shuffle all n vertices indices in the real-world graph, take the first n/2 as the offline vertices and the next n/2 as online vertices and only keep the bipartite crossing edges. |
| Hardware Specification | No | We provide such information in the supplementary material. |
| Software Dependencies | No | The paper does not explicitly mention specific software dependencies with version numbers in the main text. |
| Experiment Setup | Yes | For each plot is generated by letting each algorithm solve 10 instances for 10 different noise parameter values. For each graph G with n vertices and a given noise parameter γ [0, 1], we generate a noisy prediction b Gγ of G as follows: each online vertex v retains a random (1 γ) fraction of its true neighbors and gains a random γ fraction of its non-neighbors. For consistency ratio of 0.7, we set λLAB 0.11 and λPAW 0.51. For consistency ratio of 0.8, we set λLAB 0.29 and λPAW 0.74. For consistency ratio of 0.9, we set λLAB 0.52 and λPAW 0.89. For consistency ratio of 1.0, we set λLAB = 1 and λPAW = 1. |