We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flows whose paths contain a small number of edges, shattering the infamous ...

The planar embedding conjecture asserts that any planar metric admits an embedding into L_1 with constant distortion. This is a well-known open problem with important algorithmic implications, and has received a lot of attention over the past two ...

The classical Okamura-Seymour theorem states that for an edge-capacitated, multi-commodity flow instance in which all terminals lie on a single face of a planar graph, there exists a feasible concurrent flow if and only if the cut conditions are ...

A canonical distributed optimization problem is solving a Covering/Packing Linear Program in a distributed environment with fast convergence and low communication and space overheads. In this paper, we consider the following covering and packing ...

The multi-commodity flow problem is a classical combinatorial optimization problem that addresses a number of practically important issues of congestion and bandwidth management in connection-oriented network architectures.

We consider solutions for ...

We present the first efficient approach to global routing that takes spacing-dependent costs into account and provably finds a near-optimum solution including these costs. We show that this algorithm can be used to optimize manufacturing yield. The core ...

This paper presents three mathematical formulations for designing robust two-layer networks carrying elastic traffic. The formulations differ in the way flow reconfiguration is performed in the case of link failures. An iterative algorithm to solve the ...