A note on the subadditive network design problem

We study approximation algorithms for generalized network design where the cost of an edge depends on the identities of the demands using it (as a monotone subadditive function). Our main result is that even a very special case of this problem cannot be approximated to within a factor 2log1−ε|D| if D is the set of demands.