Learning-Augmented Algorithms for Online Steiner Tree
Authors: Chenyang Xu, Benjamin Moseley8744-8752
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We then observe that the theory is predictive of what will occur empirically. We show on graphs where terminals are drawn from a distribution, the new online algorithms have strong performance even with modestly correct predictions. [...] This section investigates the empirical performance of the proposed algorithm OAPT and IOAPT for the undirected Steiner tree problem. |
| Researcher Affiliation | Academia | Chenyang Xu 1 College of Computer Science, Zhejiang University xcy1995@zju.edu.cn, Benjamin Moseley 2 Tepper School of Business, Carnegie Mellon University moseleyb@andrew.cmu.edu |
| Pseudocode | No | The paper describes algorithms step-by-step but does not present them in a formal pseudocode block or algorithm box. |
| Open Source Code | Yes | The code is available at https://github.com/Chenyang-1995/Online-Steiner-Tree |
| Open Datasets | Yes | The road network of Bay Area is provided by The 9th DIMACS Implementation Challenge... We will sample s training instances of k terminals T1, T2, . . . Ts. |
| Dataset Splits | No | The paper describes how training instances are used for a learning algorithm and selection of a parameter, but does not provide specific train/validation/test splits with percentages or sample counts for the main experiment evaluation. |
| Hardware Specification | Yes | The experiments are conducted on a machine running Ubuntu 18.04 with an i7-7800X CPU and 48 GB memory. |
| Software Dependencies | No | The paper mentions the operating system (Ubuntu 18.04) but does not provide specific version numbers for any other software dependencies or libraries used. |
| Experiment Setup | Yes | We only consider θ {0, 0.2, 0.4, 0.6, 0.8, 1}. |