University of Sussex
Browse
LeuQuaSmoTsi11.pdf (528.83 kB)

Optimal web-scale tiering as a flow problem

Download (528.83 kB)
conference contribution
posted on 2023-06-08, 16:45 authored by Gilbert Leung, Novi QuadriantoNovi Quadrianto, Alexander Smola, Kostas Tsioutsiouliklis
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.

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 2010

Publisher

Curran Associates

Issue

23

Volume

1

Page range

1333-1341

Pages

2631.0

Book title

Proceedings of the 24th annual conference on neural information processing systems 2010

Place of publication

Red Hook, NY

ISBN

9781617823800

Series

Advances in neural information processing systems

Department affiliated with

  • Informatics Publications

Full text available

  • Yes

Peer reviewed?

  • Yes

Editors

Chris Williams, Aron Culotta, Richard Zemel, John Shawe-Taylor, John Lafferty

Legacy Posted Date

2014-02-24

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC