A Graph Theoretic Additive Approximation of Optimal Transport
Authors: Nathaniel Lahn, Deepika Mulchandani, Sharath Raghvendra
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We also provide empirical results that suggest our algorithm is competitive with respect to a sequential implementation of the Sinkhorn algorithm in execution time. Moreover, our algorithm quickly computes a solution for very small values of δ whereas Sinkhorn algorithm slows down due to numerical instability. |
| Researcher Affiliation | Academia | Nathaniel Lahn Department of Computer Science Virginia Tech Blacksburg, VA 24061 lahnn@vt.edu Deepika Mulchandani Virginia Tech Blacksburg, VA 24061 deepikak@vt.edu Sharath Raghvendra Virginia Tech Blacksburg, VA 24061 sharathr@vt.edu |
| Pseudocode | No | The algorithm's steps are described in detail within the text (e.g., Section 2.1 'The algorithm', 'First step (Hungarian Search)'), but there is no formally labeled pseudocode block or algorithm listing. |
| Open Source Code | Yes | Our implementation is available at https://github.com/nathaniellahn/Combinatorial Optimal Transport. |
| Open Datasets | Yes | All the tests are conducted on real-world data generated by randomly selecting pairs of images from the MNIST data set of handwritten digits. |
| Dataset Splits | No | The paper states it uses 'randomly selecting pairs of images from the MNIST data set' for its tests, but does not specify explicit train, validation, or test dataset splits or a partitioning methodology for the data. |
| Hardware Specification | Yes | All tests are executed on computer with a 2.40 GHz Intel Dual Core i5 processor and 8GB of RAM, using a single computation thread. |
| Software Dependencies | No | The paper states the implementation is 'written in Java' and the 'testing code is written in MATLAB', but it does not specify version numbers for these languages or any other software dependencies like libraries or solvers. |
| Experiment Setup | Yes | We implement a worst-case asymptotically optimal algorithm as presented in this paper and fix the value of ε as 0.5. |