nips nips2010 nips2010-198 nips2010-198-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Gilbert Leung, Novi Quadrianto, Kostas Tsioutsiouliklis, Alex J. Smola
Abstract: We present a fast online solver for large scale parametric max-flow problems as they occur in portfolio optimization, inventory management, computer vision, and logistics. Our algorithm solves an integer linear program in an online fashion. It exploits total unimodularity of the constraint matrix and a Lagrangian relaxation to solve the problem as a convex online game. The algorithm generates approximate solutions of max-flow problems by performing stochastic gradient descent on a set of flows. We apply the algorithm to optimize tier arrangement of over 84 million web pages on a layered set of caches to serve an incoming query stream optimally. 1
[1] P. Bartlett, E. Hazan, and A. Rakhlin. Adaptive online gradient descent. In J. C. Platt, D. Koller, Y. Singer, and S. Roweis, editors, NIPS 20, Cambridge, MA, 2008.
[2] M. J. Eisner and D. G. Severance. Mathematical techniques for efficient record segmentation in large shared databases. J. ACM, 23(4):619–635, 1976.
[3] R. Fagin. Combining fuzzy information from multiple systems. In Fifteenth ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems, pages 216–226, Montreal, Canada, 1996.
[4] L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399–404, 1956.
[5] S. Goel, J. Langford, and A. Strehl. Predictive indexing for fast search. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, NIPS, pages 505–512. MIT Press, 2008.
[6] D. Gusfield and C. U. Martel. A fast algorithm for the generalized parametric minimum cut problem and applications. Algorithmica, 7(5&6):499–519, 1992. ´
[7] D. Gusfield and E. Tardos. A faster parametric minimum-cut algorithm. Algorithmica, 11(3):278–290, 1994.
[8] I. Heller and C. Tompkins. An extension of a theorem of dantzig’s. In H. Kuhn and A. Tucker, editors, Linear Inequalities and Related Systems, volume 38 of Annals of Mathematics Studies. AMS, 1956.
[9] J. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5):604–632, 1999.
[10] V. Kolmogorov, Y. Boykov and C. Rother. Applications of parametric maxflow in computer vision. ICCV, 1–8, 2007.
[11] Y. Nesterov and J.-P. Vial. Confidence level solutions for stochastic programming. Technical Report 2000/13, Universit´ Catholique de Louvain - Center for Operations Research and e Economics, 2000.
[12] L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, Stanford, CA, USA, Nov. 1998.
[13] C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, New Jersey, 1982.
[14] M. Persin, J. Zobel, and R. Sacks-Davis. Filtered document retrieval with frequency-sorted indexes. JASIS, 47(10):749–764, 1996.
[15] K. M. Risvik, Y. Aasheim, and M. Lidal. Multi-tier architecture for web search engines. In LA-WEB, pages 132–143. IEEE Computer Society, 2003.
[16] H. S. Stone. Critical load factors in two-processor distributed systems. IEEE Trans. Softw. Eng., 4(3):254–258, 1978.
[17] H. Yan, S. Ding, and T. Suel. Inverted index compression and query processing with optimized document ordering. In J. Quemada, G. Le´ n, Y. Maarek, and W. Nejdl, editors, 18th o International Conference on World Wide Web, Madrid, Spain, pages 401–410. ACM, 2009.
[18] B. Zhang, J. Ward, and A. Feng. A simultaneous maximum flow algorithm for the selection model. Technical Report HPL-2005-91, Hewlett Packard Laboratories, 2005.
[19] B. Zhang, J. Ward, and Q. Feng. A simultaneous parametric maximum-flow algorithm for finding the complete chain of solutions. Technical Report HPL-2004-189, Hewlett Packard Laboratories, 2004.
[20] B. Zhang, J. Ward, and Q. Feng. Simultaneous parametric maximum flow algorithm with vertex balancing. Technical Report HPL-2005-121, Hewlett Packard Laboratories, 2005. 9