Online Minimum Spanning Trees with Weight Predictions

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationAlgorithms and Data Structures
EditorsPat Morin, Subhash Suri
PublisherSpringer
Publication date2023
Pages136-148
ISBN (Print)9783031389054
DOIs
Publication statusPublished - 2023
SeriesLecture Notes in Computer Science
Volume14079
ISSN0302-9743

Keywords

  • Minimum Spanning Tree
  • Online Algorithms
  • Predictions
  • Random Order Analysis

Fingerprint

Dive into the research topics of 'Online Minimum Spanning Trees with Weight Predictions'. Together they form a unique fingerprint.

Cite this