On-line generalized Steiner problem

DOI10.1016/J.TCS.2004.05.021MaRDI QIDQ1887091zbMATH OpenOpenAlexFDO

Authors Baruch Awerbuch, Yossi Azar, 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

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

Recommendations

• scientific article; zbMATH DE number 871901
• Greedy algorithms for the on-line steiner tree and generalized steiner problems
• Linear bounds for on-line Steiner problems
• scientific article; zbMATH DE number 1559550
• On-line Steiner trees in the Euclidean plane
• Online Priority Steiner Tree Problems
• Online node-weighted Steiner tree and related problems
• The sequential sum problem and performance bounds on the greedy algorithm for the on‐line Steiner problem
• Near-optimal online algorithms for prize-collecting Steiner problems
• On the rectilinear Steiner problem

Cites work

• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 1559550 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• An optimal on-line algorithm for metrical task system
• Competitive On-Line Algorithms for Distributed Data Management
• Competitive algorithms for distributed data management.
• Competitive distributed file allocation.
• Constructing Reliable Communication Networks of Small Weight Online
• Dynamic Steiner Tree Problem
• Greedy algorithms for the on-line steiner tree and generalized steiner problems
• New On-Line Algorithms for the Page Replication Problem
• On page migration and other relaxed task systems
• On-line Steiner trees in the Euclidean plane
• Online tracking of mobile users
• Steiner problem in networks: A survey
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(22)

• Group parking permit problems
• Dynamic balanced graph partitioning
• Approximating \(k\)-generalized connectivity via collapsing HSTs
• Online constrained forest and prize-collecting network design
• An \(O(\log n)\)-competitive algorithm for online constrained forest problems
• Infrastructure Leasing Problems
• Tight bounds for online weighted tree augmentation
• Tight bounds for online weighted tree augmentation
• Non-greedy online Steiner trees on outerplanar graphs
• Designing networks with good equilibria under uncertainty
• Parameterized analysis of the online priority and node-weighted Steiner tree problems
• Combinatorial optimization in system configuration design
• Greedy algorithms for online survivable network design
• A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry
• The power of deferral: maintaining a constant-competitive Steiner tree online
• Online Spanners in Metric Spaces
• Timing matters: online dynamics in broadcast games
• Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
• Online Priority Steiner Tree Problems
• Non-greedy online Steiner trees on outerplanar graphs
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• A deterministic algorithm for online Steiner tree leasing

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1887091)