We introduce networks with additive losses and gains on the arcs. If a positive flow of  x  units enter an arc  a  , then  x  +  g  ( a  ) units exit. Arcs may increase or consume flow, i.e., they are gainy or lossy. Such networks have various applications, e.g., in financial analysis, transportation, and data communication.#R##N##R##N#Problems in such networks are generally intractable. In particular, the shortest path problem is  NP  -hard. However, there is a pseudo-polynomial time algorithm for the problem with nonnegative costs and gains. The maximum flow problem is strongly  NP  -hard, even in unit-gain networks and in networks with integral capacities and loss at most three, and is hard to approximate. However, it is solvable in polynomial time in unit-loss networks using the Edmonds-Karp algorithm.#R##N##R##N#Our  NP  -hardness results contrast efficient polynomial time solutions of path and flow problems in standard and in so-called generalized networks with multiplicative losses and gains.
['Franz-Josef Brandenburg', 'Mao-cheng Cai']
Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains