Approximating some network design problems with node costs (Q638508)

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.