Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/99552
Title: Low-bandwidth routing and electrical power networks
Authors: Cook, D.
Faber, V.
Marathe, M.
Srinivasan, A. 
Sussmann, Y.J.
Issue Date: 1998
Citation: Cook, D.,Faber, V.,Marathe, M.,Srinivasan, A.,Sussmann, Y.J. (1998). Low-bandwidth routing and electrical power networks. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 1443 LNCS : 604-615. ScholarBank@NUS Repository.
Abstract: Given a graph G and a (multi-)set of pairs of vertices in it, the classical NP-hard maximum edge-dis joint-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.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/99552
ISBN: 3540647813
ISSN: 03029743
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

49
checked on Oct 5, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.