Approximating some network design problems with node costs
The authors propose approximation algorithms for several NP-hard network design problems, which are characterized by node costs in addition to edge costs. It should be noted that common network flow problems are characterized by edge costs only. The consideration of node costs is a generalization of the traditional framework (see Theorems 1.3, 1.4 and 1.5). The approximation algorithms provided in the article are important from the practical perspective. The authors use linear programming relaxations in order to obtain their bounds and this could be of some concern. However, LP solvers in the present day are extremely fast and hence it should not negatively impact the quality of their work. The problems studied in the paper under review are described extremely well, from both the formal and the informal point of view. In this regard, Sections 1.1, 1.2 and 1.3 not only describe the problems at hand but also their relations to similar problems in the literature. The material on related work is more than adequate to convince the reviewer that the authors have surveyed the field and placed their work properly within the context. The paper is extremely well-written from both the organizational and the expositional point of view. The main results are clearly laid out as well as the methods employed. I am also extremely pleased with the lemmas and theorems that I reviewed. The argument flow is clear and the techniques are sound.
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- A threshold of ln n for approximating set cover
- An algorithm for the min concave cost flow problem
- Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees
- Approximating Steiner Networks with Node Weights
- Approximating the single-sink link-installation problem in network design
- Approximation algorithms for access network design
- Approximation algorithms for constrained node weighted Steiner tree problems
- Approximation algorithms for node-weighted buy-at-bulk network design
- Approximation Schemes for the Restricted Shortest Path Problem
- Efficient recovery from power outage (extended abstract)
- Fixed-cost transportation problems
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- Improved approximating algorithms for directed Steiner forest
- Many birds with one stone
- Minimum Concave Cost Flows in Certain Networks
- Networks synthesis and optimum network design problems: Models, solution methods and applications
- On non-uniform multicommodity buy-at-bulk network design
- The One-Terminal TELPAK Problem
- A Node Splitting Technique for Two Level Network Design Problems with Transition Nodes
- Computational complexity of combinatorial distance matrix realisation
- Approximation algorithms for node-weighted directed Steiner problems
- Approximation algorithms for hop constrained and buy-at-bulk network design via hop constrained oblivious routing
This page was built for publication: Approximating some network design problems with node costs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q638508)
