Back
Online Minimum Spanning Tree with Advice
Journal article

Online Minimum Spanning Tree with Advice

Show more…
  • 2018-6-29
Published in:
  • International Journal of Foundations of Computer Science. - World Scientific Pub Co Pte Lt. - 2018, vol. 29, no. 04, p. 505-527
English In the online minimum spanning tree problem, a graph is revealed vertex by vertex; together with every vertex, all edges to vertices that are already known are given, and an online algorithm must irrevocably choose a subset of them as a part of its solution. The advice complexity of an online problem is a means to quantify the information that needs to be extracted from the input to achieve good results. For a graph of size [Formula: see text], we show an asymptotically tight bound of [Formula: see text] on the number of advice bits to produce an optimal solution for any given graph. For particular graph classes, e.g., with bounded degree or a restricted edge weight function, we prove that the upper bound can be drastically reduced; e.g., [Formula: see text] advice bits allow to compute an optimal result if the weight function equals the Euclidean distance; if the graph is complete and has two different edge weights, even a logarithmic number suffices. Some of these results make use of the optimality of Kruskal’s algorithm for the offline setting. We also study the trade-off between the number of advice bits and the achievable competitive ratio. To this end, we perform a reduction from another online problem to obtain a linear lower bound on the advice complexity for any near-optimal solution. Using our results finally allows us to give a lower bound on the expected competitive ratio of any randomized online algorithm for the problem, even on graphs with three different edge weights.
Language
  • English
Open access status
closed
Identifiers
Persistent URL
https://roar.hep-bejune.ch/global/documents/95336
Statistics
Document views: 30 File downloads: