Online node-weighted Steiner tree and related problems

DOI10.1109/FOCS.2011.65MaRDI QIDQ5494965zbMATH OpenOpenAlexFDO

Authors Joseph (Seffi) Naor, Debmalya Panigrahi, Mohit Singh

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2011.65

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Recommendations

• Near-optimal online algorithms for prize-collecting Steiner problems
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• An optimal algorithm for online prize-collecting node-weighted Steiner forest
• Parameterized analysis of the online priority and node-weighted Steiner tree problems
• scientific article; zbMATH DE number 1559550

Cited in

(33)

• The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
• An optimal algorithm for online prize-collecting node-weighted Steiner forest
• On-line generalized Steiner problem
• Timing matters: online dynamics in broadcast games
• Parameterized analysis of the online priority and node-weighted Steiner tree problems
• Non-greedy online Steiner trees on outerplanar graphs
• Approximation algorithms for priority Steiner tree problems
• scientific article; zbMATH DE number 6381651 (Why is no real title available?)
• A general approach to online network optimization problems
• Non-greedy online Steiner trees on outerplanar graphs
• Pick, pack, \& survive: charging robots in a modern warehouse based on online connected dominating sets
• The relation of connected set cover and group Steiner tree
• Online degree-bounded Steiner network design
• Online Buy-at-Bulk Network Design
• Online weighted degree-bounded Steiner networks via novel online mixed packing/covering
• The bursty Steiner tree problem
• Spider covering algorithms for network design problems
• On the hardness of full Steiner tree problems
• Greedy algorithms for online survivable network design
• Tight bounds for online weighted tree augmentation
• Near-optimal online algorithms for prize-collecting Steiner problems
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• Online Directed Spanners and Steiner Forests.
• Locating service and charging stations
• Online Spanners in Metric Spaces
• The online min-sum set cover problem
• Adaptive-adversary-robust algorithms via small copy tree embeddings
• Online spanners in metric spaces
• Online Euclidean spanners
• A nearly optimal deterministic online algorithm for non-metric facility location
• Bicriterial approximation for the incremental prize-collecting Steiner-tree problem
• Directed buy-at-bulk spanners
• Tight bounds for online weighted tree augmentation

This page was built for publication: Online node-weighted Steiner tree and related problems

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