Dynamic Programming of Optimum Flows in Lossy Communication Nets

Publisher Website
Google Scholar
Abstract
This paper deals with assignments of optimum flows in lossy communication nets. In a lossy communication net, each edgeehas an edge efficiency factor\alpha_e (0 \leq \alpha_e \leq 1)as well as an edge capacityC_e. If edgeeis an edge from nodexto nodey, then the flow\psi(e, x)entering into nodexis not only limited by the edge capacity(0 \leq \psi(e, x) \leq C_e)but also suffers a loss of(1 - \alpha_e) \cdot \psi(e, x)in passing throughe, consequently,\alpha_e \cdot \psi (e, x)emerges fromeat nodey. A flow\psiwith the sending flow value\hat{t}at the source and the receiving flow value\underbrace{t}at the sink is said to be optimum if there is no flow which has less sending flow value value thantwhile having the same receiving value\underbrace{t}. Necessary and sufficient conditions are described for the optimality of flows in Theorem 1 and Theorem 2. Based on these characterizations, dynamic programming of optimum flows in a lossy communication net is devised and demonstrated by an example.

This publication has 1 reference indexed in Scilit: