Timezone: »

 
Poster
Optimal Web-Scale Tiering as a Flow Problem
Gilbert Leung · Novi Quadrianto · Alexander Smola · Kostas Tsioutsiouliklis

Mon Dec 06 12:00 AM -- 12:00 AM (PST) @
in Poster Session and Reception »

We present a fast online solver for large scale maximum-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 80 Million web pages on a layered set of caches to serve an incoming query stream optimally. We provide an empirical demonstration of the effectiveness of our method on real query-pages data.

[ PDF] 

Author Information

Gilbert Leung (self)
Novi Quadrianto (University of Sussex and HSE)
Alexander Smola (Amazon)

**AWS Machine Learning**

Kostas Tsioutsiouliklis (Yahoo! Labs)

More from the Same Authors