Oblivious network design
Anupam Gupta, Mohammad Taghi Hajiaghayi, Harald Räcke · 2006
Consider the following network design problem: given anetwork G = (V, E), source-sink pairs {si, ti} arrive anddesire to send a unit of flow between themselves. The cost of the routing is this: if edge e carries a total of fe flow (from allthe terminal pairs), the cost is given by P e `(fe), where ` issome concave cost function; the goal is to minimize the total cost incurred. However, we want the routing to be oblivious:when terminal pair { si, ti} makes its routing decisions, itdoes not know the current flow on the edges of the network, nor the identity of the other pairs in the system. Moreover,it does not even know the identity of the function `, merelyknowing that ` is a concave function of the total flow on theedge. How should it (obliviously) route its one unit of flow? Can we get competitive algorithms for this problem?In this paper, we develop a framework to model oblivious network design problems (of which the above problemis a special case), and give algorithms with poly-logarithmic competitive ratio for problems in this framework (and hencefor this problem). Abstractly, given a problem like the one above, the solution is a multicommodity flow producing a"load " on each edge of Le = `(f1(e), f2(e),..., fk(e)),and the total cost is given by an "aggregation function" agg(Le1,..., Lem) of the loads of all edges. Our goal is todevelop oblivious algorithms that approximately minimize the total cost of the routing, knowing the aggregation func-tion agg, but merely knowing that ` lies in some class C, andhaving no other information about the current state of the network. Hence we want algorithms that are simultaneously"function-oblivious " as well as "traffic-oblivious". The aggregation functions we consider are the max andP objective functions, which correspond to the well-known measures of congestion and total cost of a network; in thispaper, we prove the following: * If the aggregation function is P, we give an oblivious algorithm with