Several practical instances of network design problems often require the network to satisfy multiple constraints. In this paper, we focus on the following problem (and its variants): find a low-cost network, under one cost function, that services every node in the graph, under another cost function, (i.e., every node of the graph is within a prespecified distance from the network). This study has important applications to the problems of optical network design and the efficient maintenance of distributed databases.
We utilize the framework developed in [MR+95] to formulate these problems as bicriteria network design problems. We present the first known approximation algorithms for the class of service-constrained network design problems. We provide a (1, O( $$\tilde \Delta$$ ln n))-approximation algorithm for the (Service cost, Total edge cost, Tree)-bicriteria problem (where $$\tilde \Delta$$ is the maximum service-degree of any node in the graph). We counterbalance this by showing that the problem does not have an (α, β)-approximation algorithm for any α ≥ 1 and β < ln n unless NP $$\subseteq$$ DTIME(n log log n ). When both the objectives are evaluated under the same cost function we provide a (2(1 + ε), 2(1 + 1/ε))-approximation algorithm, for any ε >0. In the opposite direction we provide a hardness result showing that even in the restricted case where the two cost functions are the same the problem does not have an (α, β)-approximation algorithm for α = 1 and β < ln n unless NP $$\subseteq$$ DTIME(n log log n ). We also consider a generalized Steiner forest version of the problem along with other variants involving diameter and bottleneck cost.