Improved Approximation Algorithms for Capacitated Location Routing
Authors: Jingyang Zhao, Mingyu Xiao, Shunwang Wang
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental study on benchmark instances shows that the quality of our computed solutions is better than that of the previous algorithm and is also much closer to optimality than the provable approximation factor. |
| Researcher Affiliation | Academia | Jingyang Zhao , Mingyu Xiao and Shunwang Wang University of Electronic Science and Technology of China, Chengdu, China |
| Pseudocode | Yes | Algorithm 1 An improved approximation algorithm for unsplittable and splittable CLR (Tree-Alg) ... Algorithm 2 The tree-splitting procedure for CLR ... Algorithm 3 An improved approximation algorithm for splittable CLR (Path-Alg) ... Algorithm 4 The path-splitting procedure for splittable CLR |
| Open Source Code | Yes | The detailed information of our algorithms, the 45 tested instances and the pbks can be found in https://github.com/Jingyang Zhao/CLR. |
| Open Datasets | Yes | Harks et al. [2013] tested their approximation algorithm on 45 CLR benchmark instances in total, including 36 instances from [Tuzun and Burke, 1999] and 9 instances from [Barreto et al., 2007]. |
| Dataset Splits | No | The paper states it uses "45 CLR benchmark instances" but does not specify how these instances are split into training, validation, or test sets. It refers to "previous best known solutions (pbks)" for comparison, which implies a fixed set of instances for evaluation, but no explicit split details are provided. |
| Hardware Specification | Yes | Our algorithms are implemented in C++ on a desktop computer with an AMD Ryzen 5 PRO 4650G with Radeon Graphics (3.70 GHz, 32.0 GB RAM) using Windows Subsystem for Linux (WSL). |
| Software Dependencies | No | The paper states "implemented in C++" and "using Windows Subsystem for Linux (WSL)" but does not provide specific version numbers for the C++ compiler or any other software libraries/dependencies. |
| Experiment Setup | Yes | For α, we tested different values. This choice was made because for a range of values of α the implementations can always guarantee an approximation ratio. See the following lemma. Harks et al. [2013] only considered α = 1 and showed the implementation had a ratio of 5.722. ... Table 1: The average gaps between our results and the pbks for Tree Alg and Path-Alg under different values of α |