Please use this identifier to cite or link to this item:
DC FieldValue
dc.titleLow-bandwidth routing and electrical power networks
dc.contributor.authorCook, D.
dc.contributor.authorFaber, V.
dc.contributor.authorMarathe, M.
dc.contributor.authorSrinivasan, A.
dc.contributor.authorSussmann, Y.J.
dc.identifier.citationCook, 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.
dc.description.abstractGiven 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.
dc.typeConference Paper
dc.description.sourcetitleLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.description.volume1443 LNCS
Appears in Collections:Staff Publications

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

Page view(s)

checked on May 10, 2020

Google ScholarTM



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