Small Additive Error for Unsplittable Multicommodity Flow in Outerplanar Graphs
摘要
We consider an unsplittable version of the minimum max-load multicommodity flow problem, where each demand must be routed along a single path. The objective is to minimize the maximum load on any edge in the network. In a seminal work, Schrijver, Seymour, and Winkler showed how to efficiently solve this problem on a cycle to within an additive term of \(\tfrac{3}{2}W\) of the optimal value, where W is the largest demand between any two nodes. We extend their result to outerplanar graphs and provide an efficient algorithm for this problem that exceeds the optimal value by an additive term of no more than \(O(W \log k)\) , where k is the number of faces in the graph. This implies an \(O(\log k)\) approximation ratio. We also extend this result to planar graphs with bounded treewidth and demands on the outer face, for which we also achieve an additive \(O(W \log k)\) error term.