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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Computing lower and upper bounds on the competitive ratio of onlinealgorithms is a challenging question: For a minimization combinatorial problem,proving a competitive ratio for a given algorithm leads to an upper bound.However computing lower bounds requires a proof on all algorithms. This can bemodeled as a 2-player game where a strategy for one of the players is a prooffor the lower bound. The tree representing the proof can can be foundcomputationally. This method has been used with success on the online binstretching problem where a set of items must be packed online in $m$ bins. Theitems are guaranteed to fit into the $m$ bins. However, the online proceduremight require to stretch the bins to a larger capacity in order to be able topack all the items. This stretching factor is the objective to be minimized. Wepropose original ideas to strongly improve the speed of computer searches forlower bound: propagate the game states that can be pruned from the search andimprove the speed and memory usage in the dynamic program which is used in thesearch. These improvements allowed to increase significantly the speed of thesearch and hence to prove new lower bounds for the bin stretching problem for6, 7 and 8 bins.

Online bin stretching lower bounds: Improved search of computational proofs