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

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 monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider one of the simplest and best known buffer managementarchitectures: the shared memory switch with multiple output queues and uniformpackets. It was one of the first models studied by competitive analysis, withthe Longest Queue Drop (LQD) buffer management policy shown to be at least$\sqrt{2}$- and at most $2$-competitive; a general lower bound of $4/3$ hasbeen proven for all deterministic online algorithms. Closing the gap between$\sqrt{2}$ and $2$ has remained an open problem in competitive analysis formore than a decade, with only marginal success in reducing the upper bound of$2$. In this work, we first present a simplified proof for the $\sqrt{2}$ lowerbound for LQD and then, using a reduction to the continuous case, improve thegeneral lower bound for all deterministic online algorithms from $\frac 43$ to$\sqrt{2}$. Then, we proceed to improve the lower bound of $\sqrt{2}$specifically for LQD, showing that LQD is at least $1.44546086$-competitive. Weare able to prove the bound by presenting an explicit construction of theoptimal clairvoyant algorithm which then allows for two different ways to provelower bounds: by direct computer simulations and by proving lower bounds vialinear programming. The linear programming approach yields a lower bound forLQD of $1.4427902$ (still larger than $\sqrt{2}$).

New Competitiveness Bounds for the Shared Memory Switch