Learning-Augmented Algorithms for Online Steiner Tree

This is the code for the paper "Learning-Augmented Algorithms for Online Steiner Tree".

Requirements

Python >= 3.6.11

scipy >= 1.5.4

matplotlib >= 3.3.1

Random graphs

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.

Road graphs

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.