This tutorial is devoted to the notion of max-min fairness (MMF), associated optimization
problems, and their applications to multi-commodity flow networks. We first introduce a …

Classical routing and admission control strategies achieve provably good performance by
relying on an assumption that the virtual circuits arrival pattern can be described by some a …

Recently, much attention has been devoted to the question of whether/when traditional
network protocol design, which relies on the application of algorithmic insights by human …

Let us start with two examples. A company has a machine which drills holes into printed
circuit boards. Since it produces many of these boards it wants the machine to complete one …

In this paper, we establish max-flow min-cut theorems for several important classes of
multicommodity flow problems. In particular, we show that for any n-node multicommodity …

We give a O (√ log n)-approximation algorithm for the sparsest cut, edge expansion,
balanced separator, and graph conductance problems. This improves the O (log n) …

Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing
Problems Page 1 SIAM J. COMPUT. c 2007 Society for Industrial and Applied Mathematics …

Delineating the tremendous growth in this area, the Handbook of Approximation Algorithms
and Metaheuristics covers fundamental, theoretical topics as well as advanced, practical …

The paper is concerned with tools for the quantitative analysis of finite Markov chains whose
states are combinatorial structures. Chains of this kind have algorithmic applications in many …

This paper presents fast algorithms that find approximate solutions for a general class of
problems, which we call fractional packing and covering problems. The only previously …