We give an algorithm that computes exact maximum flows and minimum-cost flows on
directed graphs with m edges and polynomially bounded integral demands, costs, and …

Cycles in graphs play an important role in many applications, eg, analysis of electrical
networks, analysis of chemical and biological pathways, periodic scheduling, and graph …

The k-server problem is perhaps the most influential online problem: natural, crisp, with a
surprising technical depth that manifests the richness of competitive analysis. The k-server …

Discrete optimization problems are everywhere, from traditional operations research
planning (scheduling, facility location and network design); to computer science databases; …

Distributed computing concerns environments in which many processors, located at different
sites, must operate in a noninterfering and cooperative manner. Each of the processors …

This book is primarily a textbook introduction to various areas of discrete geometry. In each
area, it explains several key results and methods, in an accessible and concrete manner. It …

We present algorithms for solving symmetric, diagonally-dominant linear systems to
accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where κf (A) is the …

In this paper, we show that any n point metric space can be embedded into a distribution
over dominating tree metrics such that the expected stretch of any edge is O (log n). This …

We live in a “small world,” where two arbitrary people are likely connected by a short chain
of intermediate friends. With scant information about a target individual, people can …

This paper provides a novel technique for the analysis of randomized algorithms for
optimization problems on metric spaces, by relating the randomized performance ratio for …