The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
From MaRDI portal
Publication:3460333
DOI10.1137/140955276zbMath1333.68301arXiv1307.3757OpenAlexW2259315298MaRDI QIDQ3460333
Albert Gu, Amit Kumar, Anupam Gupta
Publication date: 7 January 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1307.3757
Programming involving graphs or networks (90C35) Trees (05C05) Online algorithms; streaming algorithms (68W27)
Related Items
Multistage knapsack, Online maximum matching with recourse, Online load balancing with general reassignment cost, The power of amortized recourse for online graph problems, Online knapsack with removal and recourse, Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem, Unnamed Item, Online Maximum Matching with Recourse, Symmetry exploitation for online machine covering with bounded migration, Unnamed Item, Unnamed Item, Online multistage subset maximization problems, Relaxing the irrevocability requirement for online graph algorithms, Unnamed Item, Parameterized analysis of the online priority and node-weighted Steiner tree problems, LP-based algorithms for multistage minimization problems
Cites Work
- Unnamed Item
- Unnamed Item
- On-line Steiner trees in the Euclidean plane
- Improved bounds for on-line load balancing
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On-line generalized Steiner problem
- The Design of Approximation Algorithms
- Buyback Problem - Approximate Matroid Intersection with Cancellation Costs
- Robust Algorithms for Preemptive Scheduling
- Online Scheduling with Bounded Migration
- A Robust PTAS for Machine Covering and Packing
- The Design of Competitive Online Algorithms via a Primal—Dual Approach
- De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
- Dynamic Steiner Tree Problem
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Load Balancing for Response Time
- Online Steiner Tree with Deletions
- The power of deferral
- The Power of Recourse for Online MST and TSP
- Competitive routing of virtual circuits with unknown duration
