A solvable routing problem

Stations 1, 2, …, n are interconnected; b ij channels join stations i and j . Channels may be grouped together in cables to reruce cost. A Routing problem requires a channel layout (or network of cables) that has minimum cost. The cost of a cable is taken to be independent of its length but a function f(k) of the cable size k . That kind of cost is unusual in practice, but might be appropriate if the “cable” is actually a satellite link. Requiring f(k) to be concave gives a discount for large cables. That imposes a number of special properties on the minimizing network. An extra assumption b ij = b , a constant for all i, j , produces a solvable problem. Depending on the shape of f(k) , the solution network is either a complete graph or a particular kind of tree.