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

We design the first online algorithm with poly-logarithmic competitive ratiofor the edge-weighted degree-bounded Steiner forest(EW-DB-SF) problem and itsgeneralized variant. We obtain our result by demonstrating a new genericapproach for solving mixed packing/covering integer programs in the onlineparadigm. In EW-DB-SF we are given an edge-weighted graph with a degree boundfor every vertex. Given a root vertex in advance we receive a sequence ofterminal vertices in an online manner. Upon the arrival of a terminal we needto augment our solution subgraph to connect the new terminal to the root. Thegoal is to minimize the total weight of the solution while respecting thedegree bounds on the vertices. In the offline setting edge-weighteddegree-bounded Steiner tree (EW-DB-ST) and its many variations have beenextensively studied since early eighties. Unfortunately the recent advancementsin the online network design problems are inherently difficult to adapt fordegree-bounded problems. In contrast in this paper we obtain our result byusing structural properties of the optimal solution, and reducing the EW-DB-SFproblem to an exponential-size mixed packing/covering integer program in whichevery variable appears only once in covering constraints. We then design ageneric integral algorithm for solving this restricted family of IPs. Wedemonstrate a new technique for solving mixed packing/covering integerprograms. Define the covering frequency k of a program as the maximum number ofcovering constraints in which a variable can participate. Let m denote thenumber of packing constraints. We design an online deterministic integralalgorithm with competitive ratio of O(k log m) for the mixed packing/coveringinteger programs. We believe this technique can be used as an interestingalternative for the standard primal-dual techniques in solving online problems.

Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering