Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements

DOI10.1007/978-3-540-93980-1_14zbMath1209.68651OpenAlexW1537804457MaRDI QIDQ3602838

David P. Williamson, Yogeshwer Sharma, Chandrashekhar Nagarajan

Publication date: 12 February 2009

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-93980-1_14

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Deterministic network models in operations research (90B10) Approximation algorithms (68W25) Connectivity (05C40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the prize collecting traveling salesman problem
• Survivable networks, linear programming relaxations and the parsimonious property
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A primal-dual approximation algorithm for generalized Steiner network problems
• A New ILP Formulation for 2-Root-Connected Prize-Collecting Steiner Networks
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Tight Approximation Algorithm for Connectivity Augmentation Problems
• The prize collecting traveling salesman problem
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Approximation Algorithms for the Multi-item Capacitated Lot-Sizing Problem Via Flow-Cover Inequalities
• Sharing the cost of multicast transmissions