| Article ID: | iaor1991267 |
| Country: | United States |
| Volume: | 15 |
| Start Page Number: | 530 |
| End Page Number: | 544 |
| Publication Date: | Jul 1990 |
| Journal: | Mathematics of Operations Research |
| Authors: | Bienstock Dan, Marcotte Odile |
| Keywords: | computational analysis |
In this paper the authors study an optimization problem that arises in the design of communication networks. They show that this problem is NP-hard even when restricted to trees, and present several approximation results. In particular, the authors show that an integer programming formulation of the problem yields bounded ratio estimates for instances of the problem defined on trees.