Oblivious Buy-at-Bulk in Planar Graphs

In the oblivious buy-at-bulk network design problem in a graph, the task is to compute a fixed set of paths for every pair of source-destination in the graph, such that any set of demands can be routed along these paths. The demands could be aggregated at intermediate edges where the fusion-cost is specified by a canonical (non-negative concave) function

f

. We give a novel algorithm for planar graphs which is oblivious with respect to the demands, and is also oblivious with respect to the fusion function

f

. The algorithm is deterministic and computes the fixed set of paths in polynomial time, and guarantees a

O

(log

n

) approximation ratio for any set of demands and any canonical fusion function

f

, where

n

is the number of nodes. The algorithm is asymptotically optimal, since it is known that this problem cannot be approximated with better than Ω(log

n

) ratio. To our knowledge, this is the first tight analysis for planar graphs, and improves the approximation ratio by a factor of log

n

with respect to previously known results.