Online constrained forest and prize-collecting network design

DOI10.1007/s00453-017-0391-4zbMath1412.68302arXiv1702.04871OpenAlexW2591403913MaRDI QIDQ1755747

David P. Williamson, Seeun William Umboh, Jiawei Qian

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1702.04871

zbMATH Keywords

online algorithmscompetitive ratioprize-collecting Steiner treegeneralized Steiner tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Related Items (3)

Tight bounds for online weighted tree augmentation ⋮ Timing matters: online dynamics in broadcast games ⋮ Tight Bounds for Online Weighted Tree Augmentation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the prize collecting traveling salesman problem
• On-line generalized Steiner problem
• A primal-dual approximation algorithm for generalized Steiner network problems
• An O(logn)-Competitive Algorithm for Online Constrained Forest Problems
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• 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
• Reducibility among Combinatorial Problems
• Near-Optimal Online Algorithms for Prize-Collecting Steiner Problems
• Online and stochastic survivable network design
• Online Network Design Algorithms via Hierarchical Decompositions
• The power of deferral
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• The Power of Recourse for Online MST and TSP

This page was built for publication: Online constrained forest and prize-collecting network design