The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online

摘要: In the online Steiner tree problem, a sequence of points is revealed one-by-one: when point arrives, we only have time to add single edge connecting this previous ones, and want minimize total length edges added. Here, tight bound has been known for two decades: greedy algorithm maintains whose cost $O(\log n)$ times cost, best possible. But suppose, in addition new add, change from set edges: can do much better? Can we, e.g., maintain that constant-competitive? We answer question affirmative. give primal-dual makes swap per step (in adding ones), such tree's constant optimal cost. Our dual-based analysis quite different primal-only analyses. particular, correspondence between radii...