English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Motivated by the problem of packing Virtual Machines on physical servers in the cloud, we study the problem of online stochastic bin packing under two settings -- packing with permanent items, and packing under item departures. In the setting with permanent items, we present the first truly distribution-oblivious bin packing heuristic that achieves O(√n) regret compared to OPT for all distributions. Our algorithm is essentially gradient descent on suitably defined Lagrangian relaxation of the bin packing Linear Program. We also prove guarantees of our heuristic against non i.i.d. input using a randomly delayed Lyapunov function to smoothen the input. For the setting where items eventually depart, we are interested in minimizing the steady-state number of bins. Our algorithm extends as is to the case of item departures. Further, leveraging the Lagrangian approach, we generalize our algorithm to a setting where the processing time of an item is inflated by a certain known factor depending on the configuration it is packed in.

Lagrangian-based Online Stochastic Bin Packing