LeuQuaSmoTsi11.pdf (528.83 kB)
Optimal web-scale tiering as a flow problem
conference contribution
posted on 2023-06-08, 16:45 authored by Gilbert Leung, Novi QuadriantoNovi Quadrianto, Alexander Smola, Kostas TsioutsiouliklisWe 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.
History
Publication status
- Published
Journal
Proceedings of the 24th Annual Conference on Neural Information Advances In Neural Information Processing Systems; Vancouver, British Columbia, Canada; 6-9 December 2010Publisher
Curran AssociatesIssue
23Volume
1Page range
1333-1341Pages
2631.0Book title
Proceedings of the 24th annual conference on neural information processing systems 2010Place of publication
Red Hook, NYISBN
9781617823800Series
Advances in neural information processing systemsDepartment affiliated with
- Informatics Publications
Full text available
- Yes
Peer reviewed?
- Yes
Editors
Chris Williams, Aron Culotta, Richard Zemel, John Shawe-Taylor, John LaffertyLegacy Posted Date
2014-02-24Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC