Maximum Likelihood Analysis of the Ford–Fulkerson Method on Special Graphs

详细信息    查看全文

• 作者：Ulrich Laube ; Markus E. Nebel
• 关键词：Analysis of algorithms ; Average case ; Generating functions ; Ford–Fulkerson maxflow ; Maximum likelihood analysis ; Grid graphs ; Random geometric graphs ; Stochastic context free grammars
• 刊名：Algorithmica
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：74
• 期：4
• 页码：1224-1266
• 全文大小：1,776 KB
• 参考文献：1.Aldrich, J.: R. A. Fisher and the making of maximum likelihood 1912–1922. Stat. Sci. 12(3), 162–176 (1997)MathSciNet CrossRef MATH
  2.Chandran, B., Hochbaum, D.: A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem. Oper. Res. 57, 358–376 (2009)MathSciNet CrossRef MATH
  3.Chi, T., Geman, S.: Estimation of probabilistic context-free grammars. Comput. Linguist. 24(2), 299–308 (1998)MathSciNet
  4.Chomsky, N., Schützenberger, M.P.: The algebraic theory of context-free languages. In: Braffort, P., Hirschberg, D. (eds.) Computer Programming and Formal Languages, pp. 118–161. North Holland, New York (1963)CrossRef
  5.David, H.A., Nagaraja, H.N.: Order Statistics, 3rd edn. Wiley, New York (2003)CrossRef MATH
  6.Dinic, E.A.: An algorithm for the solution of the max-flow problem with the polynomial estimation. Sov. Math. Dokl. 11, 1277–1280 (1970). Dokl. Akad. Nauk SSSR 194, 1970, no. 4 (in Russian)
  7.Durstenfeld, R.: Algorithm 235: random permutation. Commun. ACM 7(7), 420 (1964)CrossRef
  8.Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2), 248–264 (1972)CrossRef MATH
  9.Erdos, P., Rényi, A.: On random graphs I. Publ. Math. Debr. 6, 290–297 (1959)MATH
  10.Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)CrossRef MATH
  11.Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)MATH
  12.Gilbert, E.N.: Random graphs. Ann. Math. Stat. 30, 1141–1144 (1959)CrossRef MATH
  13.Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. J. Assoc. Comput. Mach. 45, 753–782 (1998)MathSciNet CrossRef MATH
  14.Goldfab, D., Grigoriads, M.D.: A computational comparison of the dinic and network simplex methods for maximum flow. Ann. Oper. Res. 13, 83–123 (1988)MathSciNet
  15.Knuth, D.E.: The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd edn. Addison Wesley, Reading (1997)MATH
  16.Knuth, D.E.: The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd edn. Addison Wesley, Reading (1998)MATH
  17.Laube, U., Nebel, M.E.: Maximum likelihood analysis of algorithms and data structures. Theor. Comput. Sci. 411(1), 188–212 (2010)MathSciNet CrossRef MATH
  18.Motwani, R.: Average-case analysis of algorithms for matchings and related problems. J. ACM 41(6), 1329–1356 (1994)MathSciNet CrossRef MATH
  19.Orlin, J.B.: Max flows in \({O}(nm)\) time, or better. In: STOC ’13: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, pp. 765–774. ACM, New York, NY, USA (2013)
  20.Penrose, M.: Random Geometric Graphs. Oxford University Press, Oxford (2003)CrossRef MATH
  21.Sedgewick, R.: Putting the science back into computer science. www.​cs.​princeton.​edu/​rs/​talks/​ScienceCS10.​pdf (2010). Accessed 25 Nov 2014
  22.Sedgewick, R.: The role of the scientific method in programming. www.​cs.​princeton.​edu/​rs/​talks/​ScienceCS.​pdf (2010). Accessed 25 Nov 2014
  23.Sedgewick, R., Wayne, K.: Algorithms, 4th edn. Addison Wesley, Reading (2011)
  24.Vizing, V.G.: The cartesian product of graphs. Vyčisl. Sistemy 9, 30–43 (1963)MathSciNet
  25.Wild, S., Nebel, M., Reitzig, R., Laube, U.: Engineering java 7’s dual pivot quicksort using malijan. In: ALENEX 2013: Proceedings of the Meeting on Algorithm Engineering and Experiments, pp. 55–70. New Orleans, USA (2013)
  
• 作者单位：Ulrich Laube (1)
  Markus E. Nebel (1)
  
  1. Fachbereich Informatik, Technische Universität Kaiserslautern, Gottlieb-Daimler-Straße, 67663, Kaiserslautern, Germany
  
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Theory of Computation
  Mathematics of Computing
  Algorithms
  Computer Systems Organization and Communication Networks
  Data Structures, Cryptology and Information Theory
  
• 出版者：Springer New York
• ISSN：1432-0541

文摘

We present original average-case results on the performance of the Ford–Fulkerson maxflow algorithm on grid graphs (sparse) and random geometric graphs (dense). The analysis technique combines experiments with probability generating functions, stochastic context free grammars and an application of the maximum likelihood principle enabling us to make statements about the performance, where a purely theoretical approach has little chance of success. The methods lends itself to automation allowing us to study more variations of the Ford–Fulkerson maxflow algorithm with different graph search strategies and several elementary operations. A simple depth-first search enhanced with random iterators provides the best performance on grid graphs. For random geometric graphs a simple priority-first search with a maximum-capacity heuristic provides the best performance. Notable is the observation that randomization improves the performance even when the inputs are created from a random process.