A concavity result for network design problems

Abstract

The Network Design Problem has been studied extensively and in many of these models the cost is assumed to be a concave function of the loads on the links. In this paper we investigate under which conditions this is indeed the case for the communication networks. The result is presented as a theorem, the Concavity Theorem, and a list of conditions that can easily be verified. It is also shown how the theorem can be extended to other applications, like in the area of road transportation.