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 n, we show an asymptotically tight bound of (n log n) 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., 5(n ≠ 1) advice bits allow to compute an optimal result if the weight function equals the Euclidean distance; if the graph is complete and has two di erent edge weights, even a logarithmic number su ces. Some of these results make use of the optimality of Kruskal’s algorithm for the o ine setting. We also study the trade-o 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 di erent edge weights.
Online Minimum Spanning Tree with Advice / M.P. Bianchi, H. Böckenhauer, T. Brülisauer, D. Komm, B. Palano. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - 29:4(2018), pp. 505-527.
Online Minimum Spanning Tree with Advice
M.P. Bianchi
Primo
;B. PalanoUltimo
2018
Abstract
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 n, we show an asymptotically tight bound of (n log n) 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., 5(n ≠ 1) advice bits allow to compute an optimal result if the weight function equals the Euclidean distance; if the graph is complete and has two di erent edge weights, even a logarithmic number su ces. Some of these results make use of the optimality of Kruskal’s algorithm for the o ine setting. We also study the trade-o 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 di erent edge weights.File | Dimensione | Formato | |
---|---|---|---|
Copia di S0129054118410034.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
853.51 kB
Formato
Adobe PDF
|
853.51 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.