Richard M. Karp and Rajeev Motwani and Noam Nisan

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-88-392

, 1988

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-392.pdf

This paper is concerned with the design and probabilistic analysis of certain algorithms for the maximum-flow problem and related capacitated transportation problems. These algorithms run in linear time and, under certain assumptions about the probability distribution of edge capacities, obtain an optimal solution with high probability. The design of our algorithms is based on the following general method, which we call the mimicking method, for solving problems in which some of the input data is deterministic and some is random with a known distribution: <br />(i) Replace each random variable in the problem by its expectation; this gives a deterministic problem instance that has a special form, making it particularly easy to solve; <br />(ii) Solve the resulting deterministic problem instance; <br />(iii) Taking into account the actual values of the random variables, mimic the solution of the deterministic instance to obtain a near-optimal solution to the original problem; <br />(iv) Fine-tune this suboptimal solution to obtain an optimal solution. <p>We present linear time algorithms to compute a feasible flow in directed and undirected capacitated transportation problem instances. The algorithms are shown to be successful with high probability when the probability distribution of the input data satisfies certain assumptions. We also consider the maximum flow problem with multiple sources and sinks. Under probabilistic assumptions about the input, we show that with high probability the minimum cut isolates either the sources or the sinks, and we give a linear-time algorithm that produces a maximum flow with high probability.

---

BibTeX citation:

@techreport{Karp:CSD-88-392,
    Author= {Karp, Richard M. and Motwani, Rajeev and Nisan, Noam},
    Title= {Probabilistic Analysis of Network Flow Algorithms},
    Year= {1988},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/5854.html},
    Number= {UCB/CSD-88-392},
    Abstract= {This paper is concerned with the design and probabilistic analysis of certain algorithms for the maximum-flow problem and related capacitated transportation problems. These algorithms run in linear time and, under certain assumptions about the probability distribution of edge capacities, obtain an optimal solution with high probability. The design of our algorithms is based on the following general method, which we call the mimicking method, for solving problems in which some of the input data is deterministic and some is random with a known distribution:  <br />(i) Replace each random variable in the problem by its expectation; this gives a deterministic problem instance that has a special form, making it particularly easy to solve; <br />(ii) Solve the resulting deterministic problem instance;  <br />(iii) Taking into account the actual values of the random variables, mimic the solution of the deterministic instance to obtain a near-optimal solution to the original problem;  <br />(iv) Fine-tune this suboptimal solution to obtain an optimal solution.  <p>We present linear time algorithms to compute a feasible flow in directed and undirected capacitated transportation problem instances. The algorithms are shown to be successful with high probability when the probability distribution of the input data satisfies certain assumptions. We also consider the maximum flow problem with multiple sources and sinks. Under probabilistic assumptions about the input, we show that with high probability the minimum cut isolates either the sources or the sinks, and we give a linear-time algorithm that produces a maximum flow with high probability.},
}

EndNote citation:

%0 Report
%A Karp, Richard M. 
%A Motwani, Rajeev 
%A Nisan, Noam 
%T Probabilistic Analysis of Network Flow Algorithms
%I EECS Department, University of California, Berkeley
%D 1988
%@ UCB/CSD-88-392
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/5854.html
%F Karp:CSD-88-392