The power of deferral
| Autor: | Albert Gu, Anupam Gupta, Amit Kumar |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
FOS: Computer and information sciences
Fractal tree index AVL tree K-ary tree General Computer Science General Mathematics 0102 computer and information sciences 02 engineering and technology Interval tree 01 natural sciences Steiner tree problem Combinatorics symbols.namesake 020204 information systems Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) 89999 Information and Computing Sciences not elsewhere classified Vantage-point tree Mathematics Discrete mathematics Segment tree Search tree Range tree Tree (data structure) 010201 computation theory & mathematics symbols MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | STOC |
| DOI: | 10.1145/2488608.2488674 |
| Popis: | In the online Steiner tree problem, a sequence of points is revealed one-by-one: when a point arrives, we only have time to add a single edge connecting this point to the previous ones, and we want to minimize the total length of edges added. For two decades, we know that the greedy algorithm maintains a tree whose cost is O(log n) times the Steiner tree cost, and this is best possible. But suppose, in addition to the new edge we add, we can change a single edge from the previous set of edges: can we do much better? Can we maintain a tree that is constant-competitive? We answer this question in the affirmative. We give a primal-dual algorithm, and a novel dual-based analysis, that makes only a single swap per step (in addition to adding the edge connecting the new point to the previous ones), and such that the tree's cost is only a constant times the optimal cost. Previous results for this problem gave an algorithm that performed an amortized constant number of swaps: for each n, the number of swaps in the first n steps was O(n). We also give a simpler tight analysis for this amortized case. An extended abstract appears in the 45th ACM Symposium on the Theory of Computing (STOC), 2013 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|