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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In \cite{siebert2019linear} the authors present a set of integer programs(IPs) for the Steiner tree problem, which can be used for both, the directedand the undirected setting of the problem. Each IP finds an optimal Steinertree with a specific structure. A solution with the lowest cost, corresponds toan optimal solution to the entire problem. The authors show that the linearprogramming relaxation of each IP is integral and, also, that each IP ispolynomial in the size of the instance, consequently, they can be solved inpolynomial time. The main issue is that the number of IPs to solve growsexponentially with the number of terminal nodes, which makes this approachimpractical for large instances. In this paper, we propose a local searchprocedure to solve the directed Steiner tree problem using the approachpresented in \cite{siebert2019linear}. In order to do this, we present adynamic programming algorithm to solve each IP efficiently. Then we provide acharacterization of the neighborhood of each tree structure. Finally, we usethe proposed algorithm and the neighborhood characterization to solve theproblem using a simulated annealing framework. Computational experiments showthat the quality of the solutions delivered by our approach is better than theones presented in the literature for the directed Steiner tree problem.

A Simulated Annealing Algorithm for the Directed Steiner Tree Problem