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

The Virtual Network Embedding Problem (VNEP) considers the efficientallocation of resources distributed in a substrate network to a set of requestnetworks. Many existing works discuss either heuristics or exact algorithms,resulting in a choice between quick runtimes and quality guarantees for thesolutions. Recently, the first fixed-parameter tractable (FPT) approximationalgorithm for the VNEP with arbitrary request and substrate topologies has beenpublished by Rost and Schmid. This algorithm is based on a LP formulation andis FPT in the newly introduced graph parameter extraction width (EW). Ittherefore combines positive traits of heuristics and exact approaches: Theruntime is polynomial for instances with bounded EW, and the algorithm returnsapproximate solutions with high probability.  We propose two extensions of this algorithm to optimize its runtime. Firstly,we develop a new LP formulation related to tree decompositions. We show thatthis LP formulation is always smaller, and that the resulting algorithm is FPTin the new parameter extraction label width (ELW). We improve on two importantresults by Rost and Schmid: For centrally rooted half-wheel topologies, the EWscales linearly with request size, whereas the ELW is constant. Further, addingany number of paths parallel to an existing edge increases the EW by at mostthe maximum degree of the request. By contrast, the ELW only increases by atmost one. Lastly, we show that finding the minimal ELW is NP-hard.  Secondly, we consider the approach of partitioning the request into subgraphswhich are processed independently, yielding even smaller LP formulations. Whilethis algorithm may lead to higher ELW within the subgraphs, we show that thisincrease is always smaller than the size of the inter-subgraph boundary. Inparticular, the algorithm has zero additional cost when subgraphs are separatedby a single node.

Virtual Network Embedding via Decomposable LP Formulations: Orientations of Small Extraction Width and Beyond