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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The optimization version of the cavity method for single instances, calledMax-Sum, has been applied in the past to the Minimum Steiner Tree Problem onGraphs and variants. Max-Sum has been shown experimentally to giveasymptotically optimal results on certain types of weighted random graphs, andto give good solutions in short computation times for some types of realnetworks. However, the hypotheses behind the formulation and the cavity methoditself limit substantially the class of instances on which the approach givesgood results (or even converges). Moreover, in the standard model formulation,the diameter of the tree solution is limited by a predefined bound, thataffects both computation time and convergence properties. In this work wedescribe two main enhancements to the Max-Sum equations to be able to cope withoptimization of real-world instances. First, we develop an alternative 'flat'model formulation, that allows to reduce substantially the relevantconfiguration space, making the approach feasible on instances with largesolution diameter, in particular when the number of terminal nodes is small.Second, we propose an integration between Max-Sum and three greedy heuristics.This integration allows to transform Max-Sum into a highly competitiveself-contained algorithm, in which a feasible solution is given at each step ofthe iterative procedure. Part of this development participated on the 2014DIMACS challenge on Steiner Problems, and we report the results here.

Practical optimization of Steiner Trees via the cavity method