TY - GEN

T1 - Online Minimum Spanning Trees with Weight Predictions

AU - Berg, Magnus

AU - Boyar, Joan

AU - Favrholdt, Lene M.

AU - Larsen, Kim S.

N1 - https://arxiv.org/pdf/2302.12029

PY - 2023

Y1 - 2023

N2 - We consider the minimum spanning tree problem with predictions, using the weight-arrival model, i.e., the graph is given, together with predictions for the weights of all edges. Then the actual weights arrive one at a time and an irrevocable decision must be made regarding whether or not the edge should be included into the spanning tree. In order to assess the quality of our algorithms, we define an appropriate error measure and analyze the performance of the algorithms as a function of the error. We prove that, according to competitive analysis, the simplest algorithm, Follow-the-Predictions, is optimal. However, intuitively, one should be able to do better, and we present a greedy variant of Follow-the-Predictions. In analyzing that algorithm, we believe we present the first random order analysis of a non-trivial online algorithm with predictions, by which we obtain an algorithmic separation. This may be useful for distinguishing between algorithms for other problems when Follow-the-Predictions is optimal according to competitive analysis.

AB - We consider the minimum spanning tree problem with predictions, using the weight-arrival model, i.e., the graph is given, together with predictions for the weights of all edges. Then the actual weights arrive one at a time and an irrevocable decision must be made regarding whether or not the edge should be included into the spanning tree. In order to assess the quality of our algorithms, we define an appropriate error measure and analyze the performance of the algorithms as a function of the error. We prove that, according to competitive analysis, the simplest algorithm, Follow-the-Predictions, is optimal. However, intuitively, one should be able to do better, and we present a greedy variant of Follow-the-Predictions. In analyzing that algorithm, we believe we present the first random order analysis of a non-trivial online algorithm with predictions, by which we obtain an algorithmic separation. This may be useful for distinguishing between algorithms for other problems when Follow-the-Predictions is optimal according to competitive analysis.

KW - Minimum Spanning Tree

KW - Online Algorithms

KW - Predictions

KW - Random Order Analysis

U2 - 10.1007/978-3-031-38906-1_10

DO - 10.1007/978-3-031-38906-1_10

M3 - Article in proceedings

SN - 9783031389054

T3 - Lecture Notes in Computer Science

SP - 136

EP - 148

BT - Algorithms and Data Structures

A2 - Morin, Pat

A2 - Suri, Subhash

PB - Springer

ER -