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

This paper studies the online vector bin packing (OVBP) problem and therelated problem of online hypergraph coloring (OHC). Firstly, we use a doublecounting argument to prove an upper bound of the competitive ratio of$FirstFit$ for OVBP. Our proof is conceptually simple, and strengthens theresult in Azar et. al. by removing the dependency on the bin size parameter.Secondly, we introduce a notion of an online incidence matrix that is definedfor every instance of OHC. Using this notion, we provide a reduction from OHCto OVBP, which allows us to carry known lower bounds of the competitive ratioof algorithms for OHC to OVBP. Our approach significantly simplifies theprevious argument from Azar et. al. that relied on using intricate graphstructures. In addition, we slightly improve their lower bounds. Lastly, weestablish a tight bound of the competitive ratio of algorithms for OHC, whereinput is restricted to be a hypertree, thus resolving a conjecture inNagy-Gyorgy et. al. The crux of this proof lies in solving a certaincombinatorial partition problem about multi-family of subsets, which might beof independent interest.

Online Vector Bin Packing and Hypergraph Coloring Illuminated: Simpler Proofs and New Connections