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

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

zbMATH Keywords

online algorithmsSteiner treegreedyprimal-dualrecourse

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Online algorithms; streaming algorithms (68W27)

Related Items (16)

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

This page was built for publication: The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online