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

DOI10.1007/978-3-540-93980-1_14MaRDI QIDQ3602838zbMATH OpenOpenAlexFDO

Authors Chandrashekhar Nagarajan, Yogeshwer Sharma, David P. Williamson

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

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

Recommendations

• Prize-collecting Steiner network problems
• Prize-collecting steiner network problems
• Approximation algorithms for prize collecting forest problems with submodular penalty functions
• Prize-collecting survivable network design in node-weighted graphs
• scientific article; zbMATH DE number 1003253

Cites work

• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A New ILP Formulation for 2-Root-Connected Prize-Collecting Steiner Networks
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A note on the prize collecting traveling salesman problem
• A primal-dual approximation algorithm for generalized Steiner network problems
• Approximation Algorithms for the Multi-item Capacitated Lot-Sizing Problem Via Flow-Cover Inequalities
• Approximation algorithms for prize collecting forest problems with submodular penalty functions
• Network design for information networks
• Sharing the cost of multicast transmissions
• Survivable networks, linear programming relaxations and the parsimonious property
• The prize collecting traveling salesman problem
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Tight Approximation Algorithm for Connectivity Augmentation Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(6)

• Spider covers for prize-collecting network activation problem
• Approximation algorithms for prize-collecting capacitated network design problems
• Approximation algorithms for prize collecting forest problems with submodular penalty functions
• A MIP-based approach to solve the prize-collecting local access network design problem
• Prize-collecting Steiner network problems
• Prize-collecting survivable network design in node-weighted graphs

This page was built for publication: Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements

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