University of Twente Student Theses


Stochastic Minimum Spanning Tree Problem with a Single Sample

Speek, G. (2024) Stochastic Minimum Spanning Tree Problem with a Single Sample.

[img] PDF
Abstract:We consider the minimum spanning tree problem in a setting where the edge weights are stochastic instead of deterministic, and the decision maker is given only one sample of each edge’s weight distribu- tion. Under these conditions, perhaps the only reasonable strategy is to choose the spanning tree which is minimal over the sampled weights. In general, this algorithm can, in expectation, perform arbitrarily worse than the adversary that computes the minimum spanning tree over the expected weights. For exponential weights we show that the performance of this algorithm is bounded from above by the size of the largest bond in the graph, and we show that this bound is tight. Our proof is based on an inductive argument via edge contractions, that allows us to reduce the spanning tree problem to a simpler item selection problem. We also discuss a generalization to arbitrary matroids.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics MSc (60348)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page