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/

Zendy Plus

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

Zendy Tools

Zendy Open

The online (uniform) buy-at-bulk network design problem asks us to design anetwork, where the edge-costs exhibit economy-of-scale. Previous approaches tothis problem used tree- embeddings, giving us randomized algorithms. Moreover,the optimal results with a logarithmic competitive ratio requires the metric onwhich the network is being built to be known up-front; the competitive ratiosthen depend on the size of this metric (which could be much larger than thenumber of terminals that arrive).  We consider the buy-at-bulk problem in the least restrictive model where themetric is not known in advance, but revealed in parts along with the demandpoints seeking connectivity arriving online. For the single sink buy-at-bulkproblem, we give a deterministic online algorithm with competitive ratio thatis logarithmic in k, the number of terminals that have arrived, matching thelower bound known even for the online Steiner tree problem. In the obliviouscase when the buy-at-bulk function used to compute the edge-costs of thenetwork is not known in advance (but is the same across all edges), we give adeterministic algorithm with competitive ratio polylogarithmic in k, the numberof terminals.  At the heart of our algorithms are optimal constructions for online LightApproximate Shortest-path Trees (LASTs) and spanners, and their variants. Wegive constructions that have optimal trade-offs in terms of cost and stretch.We also define and give constructions for a new notion of LASTs where the setof roots (in addition to the points) expands over time. We expect thesetechniques will find applications in other online network-design problems.

LAST but not Least: Online Spanners for Buy-at-Bulk