Low-bandwidth routing and electrical power networks

TitleLow-bandwidth routing and electrical power networks
Publication TypeBook Chapters
Year of Publication1998
AuthorsCook D, Faber V, Marathe M, Srinivasan A, Sussmann Y
EditorLarsen K, Skyum S, Winskel G
Book TitleAutomata, Languages and ProgrammingAutomata, Languages and Programming
Series TitleLecture Notes in Computer Science
Pagination604 - 615
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-540-64781-2

Given a graph G and a (multi-)set of pairs of vertices in it, the classical NP-hard maximum edge-disjoint-paths problem (MDP) is to connect as many of the given pairs as possible using pairwise edge-disjoint paths in G . We study a relative of this problem: we have a network with fixed link capacities that may have to service large demands when necessary. In particular, individual demands are allowed to exceed capacities, and thus flows for some request pairs necessarily have to be split into different flow-paths. This is the framework for computational problems arising from: (i) electrical power networks due to the proposed deregulation of the electric utility industry in the USA, and (ii) applications such as real-time Internet services (e.g., telephone, fax, video). We show that these problems come in a few variants, some efficiently solvable and many NP -hard; we also present approximation algorithms for many of the NP -hard variants presented. Some of our approximation algorithms benefit from certain improved tail estimates that we derive; the latter also yield improved approximations for a family of packing integer programs.