Approximation algorithms for concave cost network flow problems

The cost structures for resource allocation in many network design problems obey economies of scale, meaning that the cost per unit resource becomes cheaper as the amount of resources allocated increases. For instance, if we are purchasing cables to route data in a network, the cost per unit bandwidth reduces as the bandwidth we need to route increases. Another feature of resource allocation is granularity, meaning that the resource can only be purchased in multiples of a certain minimum quantity. Again, in the context of purchasing cables in a network, the minimum capacity cable available might be a T1 line with capacity 1 Mbps.; We consider various problems involving allocating resources to serve user demand in a network, where the goal is to optimize the cost of allocation. These resources could be cables to route bandwidth or web caches to serve content, among other possibilities. The issues of granularity and economies of scale in the cost structure make these problems NP-Hard, which means it is unlikely that the optimal solution can be found efficiently.; These cost functions can be modeled as non-decreasing concave functions of the user demand. The resource allocation problems are therefore concave cost flow problems. As mentioned above, these problems are NP-Hard.; We first discuss various network design problems that fall in the concave cost flow frame-work. We then present efficient polynomial time algorithms for finding solutions whose cost is provably close to the cost of the optimal solution. We consider various general and special cases of concave functions and obtain combinatorial algorithms with good performance guarantees. For the general concave function case, we obtain a logarithmic approximation ratio, meaning that the cost of the solution we find is always within a logarithmic factor of the optimal solution. For the special case where the cost function is defined over a metric space, we obtain a constant factor approximation ratio. These algorithms, in addition to having good performance guarantees, are simple to implement and efficient in practice.