This is the code for the paper "Learning-Augmented Algorithms for Online Steiner Tree".
Python >= 3.6.11
scipy >= 1.5.4
matplotlib >= 3.3.1
To do the robustness experiments, run
python robustness_random_graph.py
To obtain the learnability performance of uniform distribution and two-class distribution, run
python learnability_random_graph_uniform_distri.py
and
python learnability_random_graph_twoclass_distri.py
respectively.
We give 4 text files in road_graph/, each corresponding to a road graph. In each file, a row (u,v,w) respresents the edge (u,v) with cost w.
To do the robustness experiments, run
python robustness_road_graph.py
To obtain the learnability performance of cluster distribution, run
python learnability_road_graph_cluster_distri.py
The number of terminals sampled per cluster is 100 by default.
Some functions are provided in draw.py, which could be useful when drawing figures for the experiments.
We thank Mirko Giacchini for the discussion on some implementation details of the proposed algorithms.