On-line generalized Steiner problem

DOI10.1016/j.tcs.2004.05.021zbMath1102.68088OpenAlexW1981114903MaRDI QIDQ1887091

Yossi Azar, Baruch Awerbuch, Yair Bartal

Publication date: 23 November 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.05.021

zbMATH Keywords

Steiner treeSteiner forestOnlineCompetitive

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Related Items (20)

Tight bounds for online weighted tree augmentation ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ Online Priority Steiner Tree Problems ⋮ The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online ⋮ Non-greedy online Steiner trees on outerplanar graphs ⋮ Group parking permit problems ⋮ Timing matters: online dynamics in broadcast games ⋮ Unnamed Item ⋮ Online Spanners in Metric Spaces ⋮ Non-greedy Online Steiner Trees on Outerplanar Graphs ⋮ Dynamic Balanced Graph Partitioning ⋮ A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ An O(logn)-Competitive Algorithm for Online Constrained Forest Problems ⋮ Online constrained forest and prize-collecting network design ⋮ Online Node-weighted Steiner Forest and Extensions via Disk Paintings ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ Tight Bounds for Online Weighted Tree Augmentation ⋮ Combinatorial optimization in system configuration design ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On-line Steiner trees in the Euclidean plane
• Competitive algorithms for distributed data management.
• Competitive distributed file allocation.
• Steiner problem in networks: A survey
• Dynamic Steiner Tree Problem
• New On-Line Algorithms for the Page Replication Problem
• Competitive On-Line Algorithms for Distributed Data Management
• An optimal on-line algorithm for metrical task system
• Constructing Reliable Communication Networks of Small Weight Online
• Online tracking of mobile users
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Greedy algorithms for the on-line steiner tree and generalized steiner problems
• On page migration and other relaxed task systems

This page was built for publication: On-line generalized Steiner problem