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

In this work, we consider online vector bin packing. It is known that noalgorithm can have a competitive ratio of $o(d/\log^2 d)$ in the absolutesense, though upper bounds for this problem were always shown in the asymptoticsense. Since variants of bin packing are traditionally studied with respect tothe asymptotic measure and since the two measures are different, we focus onthe asymptotic measure and prove new lower bounds on the asymptotic competitiveratio. The existing lower bounds prior to this work were much smaller than $3$even for very large dimensions.  We significantly improve the best known lower bounds on the asymptoticcompetitive ratio (and as a byproduct, on the absolute competitive ratio) foronline vector packing of vectors with $d \geq 3$ dimensions, for every suchdimension $d$. To obtain these results, we use several different constructions,one of which is an adaptive construction showing a lower bound of$\Omega(\sqrt{d})$. Our main result is that the lower bound of $\Omega(d/\log^2d)$ on the competitive ratio holds also in the asymptotic sense. The lastresult requires a careful adaptation of constructions for online coloringrather than simple black-box reductions.

Truly asymptotic lower bounds for online vector bin packing