Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
Authors: Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We implement the factor-revealing LP in Section 3 for all possible values of β, β [1, 100] where β > β . The largest approximation ratio that we obtain using the factorrevealing LP is 0.6774 which is achieved for parameter β = 6 and β = 5 (see Table 1 and Figure 3). The experiments were conducted on a computing cluster equipped with 64 cores, each running at 2.30GHz on Intel(R) Xeon(R) processors, and with 756 Gi B of main memory. |
| Researcher Affiliation | Academia | 1Khoury College of Computer Science, Northeastern University, Boston, USA 2Department of Management Science and Engineering, Stanford University, Stanford, USA. |
| Pseudocode | Yes | LP 1: The factor-revealing LP for the approximation ratio of (β, β )-EDCS |
| Open Source Code | Yes | All of our code3 is written in Python (version 3.10.12) and is available in the supplementary material. ... 3The implemented code can be found at the following link. |
| Open Datasets | No | The paper analyzes a theoretical approximation ratio using a linear program and numerical solutions, rather than training a model on a traditional dataset. Therefore, there is no mention of a public or open dataset for training. |
| Dataset Splits | No | The paper does not involve traditional machine learning experiments with train/validation/test splits of data. It focuses on numerical solutions to a linear program. Therefore, no specific dataset split information for validation is provided. |
| Hardware Specification | Yes | The experiments were conducted on a computing cluster equipped with 64 cores, each running at 2.30GHz on Intel(R) Xeon(R) processors, and with 756 Gi B of main memory. |
| Software Dependencies | Yes | All of our code3 is written in Python (version 3.10.12)... For solving factorrevealing LP instances, we utilized the Gurobi optimization package (version 11.0.0). |
| Experiment Setup | Yes | We implement the factor-revealing LP in Section 3 for all possible values of β, β [1, 100] where β > β . The largest approximation ratio that we obtain using the factorrevealing LP is 0.6774 which is achieved for parameter β = 6 and β = 5. |