A Faster Maximum Cardinality Matching Algorithm with Applications in Machine Learning
Authors: Nathaniel Lahn, Sharath Raghvendra, Jiacheng Ye
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 4 Experimental results In this section, we compare the performance of the HK and LR algorithms when applied to computing an exact bottleneck matching between equal-sized point sets A, B R2 drawn uniformly at random from a unit square, where n = |A| + |B|. |
| Researcher Affiliation | Academia | Nathaniel Lahn School of Computing and Information Sciences Radford University Radford, VA 24142 nlahn@radford.edu Sharath Raghvendra Department of Computer Science Virginia Tech Blacksburg, VA 24061 sharathr@vt.edu Jiacheng Ye Department of Computer Science Virginia Tech Blacksburg, VA 24061 yjc0513@vt.edu |
| Pseudocode | No | The paper describes the algorithms in prose but does not include any structured pseudocode or algorithm blocks (e.g., a figure or section explicitly labeled "Algorithm" or "Pseudocode"). |
| Open Source Code | Yes | Our implementations of our algorithm and HK can be found at https://github.com/nathaniellahn/JOCGV3 |
| Open Datasets | No | The paper states: "For each run, we uniformly sample points from a unit square to obtain the point sets A and B." This indicates that data was generated, not taken from a publicly available or open dataset with provided access information. |
| Dataset Splits | No | The paper describes the generation of point sets A and B for experiments but does not provide specific details on training, validation, or test dataset splits (e.g., percentages, sample counts, or citations to predefined splits). |
| Hardware Specification | Yes | We execute our experiments on a server running Cent OS Linux 7, with 12 Intel E5-2683v4 cores and 128GB of RAM. |
| Software Dependencies | No | The paper mentions the operating system "Cent OS Linux 7" for the server used in experiments, but it does not provide specific version numbers for any key software components, libraries, or frameworks (e.g., Python version, PyTorch/TensorFlow version, compiler version, etc.) that would be necessary for reproducible software dependencies. |
| Experiment Setup | Yes | For each value of n in {100, 1000, 5000, 10000, 50000, 100000, 500000, 1000000, 1500000}, we execute 10 runs. For each run, we uniformly sample points from a unit square to obtain the point sets A and B. Next, we compute a bottleneck matching between A and B separately, using both the HK algorithm and our algorithm, and record performance metrics for both algorithms. ...When guessing the bottleneck distance for each run, instead of enforcing that the number of guesses is O(log n) it is sufficient in practice to continue the binary search on δ until the relative error becomes less than a sufficiently small value ε (see Section D of the supplement). Both the HK-based algorithm and the LR-based algorithm use the same strategy for guessing the bottleneck distance in the experiments. |