Improved Approximation Algorithms for Clustered TSP and Subgroup Planning
Authors: Jingyang Zhao, Mingyu Xiao, Junqiang Peng, Ziliang Xiong
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We also conduct experiments to evaluate the performance of our algorithms. Experiments We conduct experiments to evaluate the performance of our algorithms. There are mainly two experiments. The first experiment is to compare our first FPT approximation algorithm with the previous FPT 2.5-approximation algorithm (Sumita et al. 2017), which is denoted as SYKK. [...] In the second experiment, we test our second FPT algorithm, Alg.4, and compare it with our polynomial-time algorithms Alg.1 and Alg.2. |
| Researcher Affiliation | Academia | Jingyang Zhao, Mingyu Xiao*, Junqiang Peng, Ziliang Xiong University of Electronic Science and Technology of China |
| Pseudocode | Yes | Algorithm 1: The first algorithm for SGPP (Alg.1) ... Algorithm 2: The second algorithm for SGPP (Alg.2) ... Algorithm 3: The third algorithm for SGPP (Alg.3) ... Algorithm 4: The fourth algorithm for SGPP (Alg.4) |
| Open Source Code | Yes | Our code is available at https://github.com/forgottencsc/The Subgroup Planning Problem. |
| Open Datasets | Yes | Similarly to (Sumita et al. 2017), we use VLSI datasets1 for TSP. The datasets consist of 102 instances with the size ranging from 131 to 744,710. 1http://www.math.uwaterloo.ca/tsp/vlsi/index.html |
| Dataset Splits | No | For each instance, we generate a set of pairwise disjoint groups of the same size t by randomly creating groups: we first sort all vertices uniformly at random, and then sequentially select t vertices to create a group. Note that a random method was also used in (Sumita et al. 2017). This sentence describes the method of generating problem instances for evaluation, not typical training/test/validation splits for a machine learning model. |
| Hardware Specification | Yes | Our algorithm is implemented in C++ and tested on a server with an Intel Xeon Gold 6226R CPU @ 2.90GHz and 512 GB of memory, running Ubuntu Server 20.04 LTS. |
| Software Dependencies | No | Our algorithm is implemented in C++ and tested on a server with an Intel Xeon Gold 6226R CPU @ 2.90GHz and 512 GB of memory, running Ubuntu Server 20.04 LTS. The paper only specifies the programming language (C++) and the operating system with its version (Ubuntu Server 20.04 LTS), but no specific libraries, frameworks, or compilers with version numbers. |
| Experiment Setup | Yes | In the first experiment, we need to set t as small values since the running of Alg.4 is O (2t). ...Therefore, we consider t {5, 10, 15}. ... In this experiment, we set m as small values on small instances. In detail, we consider m {4, 6, 8, 10, 12}. ... we set the weight of each edge uv within each group to X d(u, v), where d(u, v) is the original distance between u and v, and X is an integer drawn uniformly at random from the range [2, 10]. |