Approximating some network design problems with node costs
type: Item
instance of: scholarly article
title: Approximating some network design problems with node costs
zbMATH Open document ID: 1236.68297
author: Guy Kortsarz
author: Zeev Nutov
published in: Theoretical Computer Science
publication date: 2011-09-12T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C21
zbMATH DE Number: 5947147
zbMATH Keywords: approximation algorithms
zbMATH Keywords: Steiner trees
zbMATH Keywords: computational complexity
zbMATH Keywords: network flows
zbMATH Keywords: integrality gap
reviewed by: K. Subramani
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.04.013
OpenAlex ID: W3023424394
cites work: Approximation algorithms for access network design
cites work: Fixed-cost transportation problems
cites work: On non-uniform multicommodity buy-at-bulk network design
cites work: Q2934722
cites work: A threshold of ln n for approximating set cover
cites work: Q4633905
cites work: Q4198056
cites work: An algorithm for the min concave cost flow problem
cites work: The One-Terminal TELPAK Problem
cites work: Efficient recovery from power outage (extended abstract)
cites work: Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees
cites work: Approximation Schemes for the Restricted Shortest Path Problem
cites work: A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
cites work: Bicriteria Network Design Problems
cites work: Networks synthesis and optimum network design problems: Models, solution methods and applications
cites work: Approximation algorithms for constrained for constrained node weighted steiner tree problems
cites work: Approximating Steiner Networks with Node Weights
cites work: Many birds with one stone
cites work: Q4527015
cites work: Approximating the single-sink link-installation problem in network design
cites work: Minimum Concave Cost Flows in Certain Networks
DOI: 10.1016/J.TCS.2011.04.013
description: scientific article; zbMATH DE number 5947147