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

In the \emph{budgeted rooted node-weighted Steiner tree} problem, we aregiven a graph $G$ with $n$ nodes, a predefined node $r$, two weights associatedto each node modelling costs and prizes. The aim is to find a tree in $G$rooted at $r$ such that the total cost of its nodes is at most a given budget$B$ and the total prize is maximized. In the \emph{quota rooted node-weightedSteiner tree} problem, we are given a real-valued quota $Q$, instead of thebudget, and we aim at minimizing the cost of a tree rooted at $r$ whose overallprize is at least $Q$.  For the case of directed graphs with additive prize function, we develop atechnique resorting on a standard flow-based linear programming relaxation tocompute a tree with good trade-off between prize and cost, which allows us toprovide very simple polynomial time approximation algorithms for both thebudgeted and the quota problems. For the \emph{budgeted} problem, our algorithmachieves a bicriteria $(1+\epsilon,O(\frac{1}{\epsilon^2}n^{2/3}\ln{n}))$-approximation, for any $\epsilon \in (0,1]$. For the \emph{quota} problem, our algorithm guarantees a bicriteriaapproximation factor of $(2, O(n^{2/3}\ln{n}))$. Next, by using the flow-basedLP, we provide a surprisingly simple polynomial time $O((1+\epsilon)\sqrt{n}\ln {n})$-approximation algorithm for the node-weighted version of the directedSteiner tree problem, for any $\epsilon>0$.  For the case of undirected graphs with monotone submodular prize functionsover subsets of nodes, we provide a polynomial time$O(\frac{1}{\epsilon^3}\sqrt{n}\log{n})$-approximation algorithm for thebudgeted problem that violates the budget constraint by a factor of at most$1+\epsilon$, for any $\epsilon \in (0, 1]$. Our technique allows us to providea good approximation also for the quota problem.

Approximation algorithms for Node-weighted Steiner Problems: Digraphs with Additive Prizes and Graphs with Submodular Prizes