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

Recently, Renault (2016) studied the dual bin packing problem in theper-request advice model of online algorithms. He showed that given$O(1/\epsilon)$ advice bits for each input item allows approximating the dualbin packing problem online to within a factor of $1+\epsilon$. Renault askedabout the advice complexity of dual bin packing in the tape-advice model ofonline algorithms. We make progress on this question. Let $s$ be the maximumbit size of an input item weight. We present a conceptually simple onlinealgorithm that with total advice $O\left(\frac{s + \log n}{\epsilon^2}\right)$approximates the dual bin packing to within a $1+\epsilon$ factor. To this end,we describe and analyze a simple offline PTAS for the dual bin packing problem.Although a PTAS for a more general problem was known prior to our work(Kellerer 1999, Chekuri and Khanna 2006), our PTAS is arguably simpler to stateand analyze. As a result, we could easily adapt our PTAS to obtain theadvice-complexity result.  We also consider whether the dependence on $s$ is necessary in our algorithm.We show that if $s$ is unrestricted then for small enough $\epsilon > 0$obtaining a $1+\epsilon$ approximation to the dual bin packing requires$\Omega_\epsilon(n)$ bits of advice. To establish this lower bound we analyzean online reduction that preserves the advice complexity and approximationratio from the binary separation problem due to Boyar et al. (2016). We definetwo natural advice complexity classes that capture the distinction similar tothe Turing machine world distinction between pseudo polynomial time algorithmsand polynomial time algorithms. Our results on the dual bin packing problemimply the separation of the two classes in the advice complexity world.

A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version