Robustification of Online Graph Exploration Methods
Authors: Franziska Eberle, Alexander Lindermayr, Nicole Megow, Lukas Nölke, Jens Schlöter9732-9740
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We provide theoretical worst-case bounds that gracefully degrade with the prediction error, and we complement them by computational experiments that confirm our results. Further, we extend our concept to a general framework to robustify algorithms. [...] We complement our theoretical results by empirically evaluating the performance of our algorithms on several real-world instances as well as artificially generated instances. The results confirm the power of using predictions and the effectivity of the robustification framework. |
| Researcher Affiliation | Academia | Franziska Eberle,1 Alexander Lindermayr,2 Nicole Megow,2 Lukas N olke,2 Jens Schl oter2 1 Department of Mathematics, London School of Economics 2 Faculty of Mathematics and Computer Science, University of Bremen |
| Pseudocode | Yes | Algorithm 1: Robustification scheme R. [...] Algorithm 2: Computes next unexplored node visited by A and updates GA. |
| Open Source Code | No | The paper does not provide explicit statements about releasing source code for its own methodology, nor does it provide a direct link to a code repository. It mentions third-party tools like OSMnx. |
| Open Datasets | Yes | We analyze the performance of the robustification scheme for various instances, namely, real world city road networks, symmetric graphs of the TSPlib library (Reinelt 1991, 1995), and special artificial graphs. [...] built with OSMnx (Boeing 2017) from Open Street Map data (Open Street Map contributors 2017). |
| Dataset Splits | No | The paper mentions using specific instances like TSPLib and Rosenkrantz graphs, but it does not specify explicit training, validation, or test dataset splits (e.g., percentages, sample counts, or references to predefined splits). |
| Hardware Specification | No | The paper does not provide any specific hardware details such as CPU or GPU models, memory specifications, or types of computing clusters used for running the experiments. |
| Software Dependencies | No | The paper mentions using 'OSMnx (Boeing 2017)' for building road networks, but it does not provide specific version numbers for OSMnx or any other key software libraries or solvers used in the experiments, which would be necessary for reproducibility. |
| Experiment Setup | Yes | The parameter λ can steer the algorithm towards one of the underlying algorithms, e.g., towards NN when λ . It reflects our trust in the quality of the provided predictions. [...] For each instance, we generate 150 predictions with relative errors ranging from 0 up to 30. [...] with robustification parameters 0, 1, and 20, respectively. |