Online Minimum Spanning Tree with Advice
| Autor: | Dennis Komm, Beatrice Palano, Tatjana Brülisauer, Maria Paola Bianchi, Hans-Joachim Böckenhauer |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Computer science Online algorithm Advice complexity Online minimum spanning tree problem 0102 computer and information sciences 02 engineering and technology Strength of a graph Minimum spanning tree 01 natural sciences Graph Vertex (geometry) Combinatorics Circulant graph Kruskal's algorithm 010201 computation theory & mathematics 020204 information systems Reverse-delete algorithm 0202 electrical engineering electronic engineering information engineering Computer Science (miscellaneous) Regular graph Feedback vertex set Graph factorization Advice (complexity) Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | International Journal of Foundations of Computer Science, 29 (4) Lecture Notes in Computer Science ISBN: 9783662491911 |
| ISSN: | 1793-6373 0129-0541 |
| DOI: | 10.1142/s0129054118410034 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|