## Abstract

Gupta et al. [13] introduced a very general multi-commodity flow problem in which the cost of a given flow solution on a graph G = (V, E) is calculated by first computing the link loads via a load-function ℓ, that describes the load of a link as a function of the flow traversing the link, and then aggregating the individual link loads into a single number via an aggregation function agg: ℝ^{|E|} → ℝ. In this paper we show the existence of an oblivious routing scheme with competitive ratio O(log n) and a lower bound of Ω(log n/log log n) for this model when the aggregation function agg is an L_{p}-norm. Our results can also be viewed as a generalization of the work on approximating metrics by a distribution over dominating tree metrics (see e.g. [4], [5], [8]) and the work on minimum congestion oblivious routing [20], [14], [21]. We provide a convex combination of trees such that routing according to the tree distribution approximately minimizes the L_{p}-norm of the link loads. The embedding techniques of Bartal [4], [5] and Fakcharoenphol et al. [8] can be viewed as solving this problem in the Li-norm while the result of Räcke [21] solves it for L _{∞}. We give a single proof that shows the existence of a good tree-based oblivious routing for any L_{p}-norm. For the Euclidean norm, we also show that it is possible to compute a tree-based oblivious routing scheme in polynomial time.

Original language | English |
---|---|

Title of host publication | Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009 |

Pages | 32-40 |

Number of pages | 9 |

DOIs | |

State | Published - 2009 |

Externally published | Yes |

Event | 50th Annual Symposium on Foundations of Computer Science, FOCS 2009 - Atlanta, GA, United States Duration: 25 Oct 2009 → 27 Oct 2009 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

ISSN (Print) | 0272-5428 |

### Conference

Conference | 50th Annual Symposium on Foundations of Computer Science, FOCS 2009 |
---|---|

Country/Territory | United States |

City | Atlanta, GA |

Period | 25/10/09 → 27/10/09 |

## Keywords

- Metric embeddings
- Norm
- Oblivious routing

## Fingerprint

Dive into the research topics of 'Oblivious routing for the L_{p}-norm'. Together they form a unique fingerprint.