Estimation of flows in flow networks

Let G be a directed graph with an unknown flow on each edge such that the following flow conservation constraint is maintained: except for sources and sinks, the sum of flows into a node equals the sum of flows going out of a node. Given a noisy measurement of the flow on each edge, the problem we address, which we call the Most Probable Flow Estimation problem (MPFE), is to estimate the most probable assignment of flow for every edge such that the flow conservation constraint is maintained. We provide an algorithm called ΔY-mpfe for solving the MPFE problem when the measurement error is Gaussian (Gaussian-MPFE). The algorithm works in O(|E| + |V|²) when the underlying undirected graph of G is a 2-connected planar graph, and in O(|E| + |V|) when it is a 2-connected serial–parallel graph or a tree. This result is applicable to any Minimum Cost Flow problem for which the cost function is τe(Xe − μe)² for edge e where μe and τe are constants, and Xe is the flow on edge e. We show that for all topologies, the Gaussian-MPFE's precision for each edge is analogous to the equivalent resistance measured in series to this edge in an electrical network built by replacing every edge with a resistor reflecting the measurement's precision on that edge.