A Robust Exact Algorithm for the Euclidean Bipartite Matching Problem
Authors: Akshaykumar Gattani, Sharath Raghvendra, Pouyan Shirzadian
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we present the results of our experiments comparing the execution time of our algorithm to that of the Hungarian algorithm. |
| Researcher Affiliation | Academia | Akshaykumar G. Gattani1, Sharath Raghvendra1, and Pouyan Shirzadian1 1Department of Computer Science, Virginia Tech |
| Pseudocode | Yes | The pseudo-code of our divide-and-conquer algorithm is provided in Algorithm 1. |
| Open Source Code | Yes | Our implementations are available at https://github.com/agattani190/Exact-Euclidean-Bipartite-Matching. |
| Open Datasets | Yes | For a real-world dataset, we employ the New York Taxi dataset [47] and obtain two distributions, namely (i) the distribution of pickup locations (Pickup) and (ii) the distribution of drop-off locations (Drop-off) of passengers. We filtered the datasets by considering trips in seven dates in 2014 with (i) a trip duration of at least 3 minutes, and (ii) a trip velocity of at most 110mph. ... [47] NYC Taxi and Limousine Commission (TLC). Trip record data. https://www.nyc.gov/ site/tlc/about/tlc-trip-record-data.page, 2023. Accessed: 2023-03-01. |
| Dataset Splits | No | The paper describes the synthetic and real-world datasets used and how samples were drawn but does not specify train, validation, or test splits by percentages or sample counts, nor does it mention cross-validation. |
| Hardware Specification | Yes | All computations are performed using a single calculation thread on a computer with a 2.6 GHz 6-Core Intel Core i7 CPU and 16 GB of 2667 MHz DDR4 RAM. |
| Software Dependencies | No | The paper states "Both algorithms are implemented in Java" and "we use the classical implementation of Dijkstra s shortest path algorithm" but does not provide specific version numbers for Java or any other software components. |
| Experiment Setup | Yes | For the synthetic dataset, we use two distributions, namely (i) a uniform distribution defined on the unit square (Uniform), and (ii) a Gaussian distribution constrained to the unit square with a randomly chosen mean inside the unit square and a standard deviation of 0.25 (Gaussian). For a real-world dataset, we employ the New York Taxi dataset [47] and obtain two distributions... We filtered the datasets by considering trips in seven dates in 2014 with (i) a trip duration of at least 3 minutes, and (ii) a trip velocity of at most 110mph. ... In each test, we conducted experiments using two sets of n i.i.d samples from distributions µ and ν within the unit square. |