Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements
DOI10.1007/978-3-540-93980-1_14zbMATH Open1209.68651OpenAlexW1537804457MaRDI QIDQ3602838FDOQ3602838
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
Recommendations
Deterministic network models in operations research (90B10) Approximation algorithms (68W25) Connectivity (05C40) Network design and communication in computer systems (68M10)
Cites Work
- The prize collecting traveling salesman problem
- A General Approximation Technique for Constrained Forest Problems
- A note on the prize collecting traveling salesman problem
- Title not available (Why is that?)
- 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
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Network design for information networks
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- Sharing the cost of multicast transmissions
- Approximation algorithms for prize collecting forest problems with submodular penalty functions
- Survivable networks, linear programming relaxations and the parsimonious property
- A primal-dual approximation algorithm for generalized Steiner network problems
- A New ILP Formulation for 2-Root-Connected Prize-Collecting Steiner Networks
- Tight Approximation Algorithm for Connectivity Augmentation Problems
Cited In (6)
- 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
- Spider covers for prize-collecting network activation problem
- Approximation algorithms for prize-collecting capacitated network design problems
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)
