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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Best-Fit is one of the most prominent and practically used algorithms for thebin packing problem, where a set of items with associated sizes needs to bepacked in the minimum number of unit-capacity bins. Kenyon [SODA '96] studiedonline bin packing under random-order arrival, where the adversary chooses thelist of items, but the items arrive one by one according to an arrival orderdrawn uniformly randomly from the set of all permutations of the items.Kenyon's seminal result established an upper bound of $1.5$ and a lower boundof $1.08$ on the random-order ratio of Best-Fit, and it was conjectured thatthe true ratio is $\approx 1.15$. The conjecture, if true, will also imply thatBest-Fit (on randomly permuted input) has the best performance guarantee amongall the widely-used simple algorithms for (offline) bin packing. Thisconjecture has remained one of the major open problems in the area, ashighlighted in the recent survey on random-order models by Gupta and Singla[Beyond the Worst-Case Analysis of Algorithms '20]. Recently, Albers et al.[Algorithmica '21] improved the upper bound to $1.25$ for the special case whenall the item sizes are greater than $1/3$, and they improve the lower bound to$1.1$. Ayyadevara et al. [ICALP '22] obtained an improved result for thespecial case when all the item sizes lie in $(1/4, 1/2]$, which corresponds tothe $3$-partition problem. The upper bound of $3/2$ for the general case,however, has remained unimproved.  In this paper, we make the first progress towards the conjecture, by showingthat Best-Fit achieves a random-order ratio of at most $1.5 - \varepsilon$, fora small constant $\varepsilon>0$. Furthermore, we establish an improved lowerbound of $1.144$ on the random-order ratio of Best-Fit, nearly reaching theconjectured ratio.

Bin Packing under Random-Order: Breaking the Barrier of 3/2