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 Pro

Presents the zaia usage as premium feature

ZAIA

Presents AI Discovery search usage as a premium feature

AI Discovery

Presents AI Discovery explain and summary usage as a premium feature

Content Analysis

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Presents the pdf analysis as premium feature

PDF Analysis

1500 Top-up

3000 Top-up

Zendy Basic

2500 Top-up

Zendy Unlimited

Presents the access of premium content as premium feature

Premium Content

The  problem, also known as the multiterminal cut problem, is defined on an edge-weighted graph with  k  distinct vertices called “terminals.” The goal is to remove a minimum weight collection of edges from the graph such that there is no path between any pair of terminals. The problem is APX-hard. Isolating cuts are minimum cuts which separate one terminal from the rest. The union of all the isolating cuts, except the largest, is a    $$(2-2/k)$$  ( 2 - 2 / k ) -approximation to the optimal k-terminal cut. An instance of  is    $$\gamma $$  γ -stable if edges in the cut can be multiplied by up to    $$\gamma $$  γ without changing the unique optimal solution. In this paper, we show that, in any    $$(k-1)$$  ( k - 1 ) -stable instance of , the source sets of the isolating cuts are the source sets of the unique optimal solution to that  instance. We conclude that the    $$(2-2/k)$$  ( 2 - 2 / k ) -approximation algorithm returns the optimal solution on    $$(k-1)$$  ( k - 1 ) -stable instances. Ours is the first result showing that this    $$(2-2/k)$$  ( 2 - 2 / k ) -approximation is an exact optimization algorithm on a special class of graphs. We also show that our    $$(k-1)$$  ( k - 1 ) -stability result is tight. We construct    $$(k-1-\epsilon )$$  ( k - 1 - ϵ ) -stable instances of the  problem which only have trivial isolating cuts: that is, the source set of the isolating cuts for each terminal is just the terminal itself. Thus, the    $$(2-2/k)$$  ( 2 - 2 / k ) -approximation does not return an optimal solution.

Solving $$(k-1)$$-stable instances of k-terminal cut with isolating cuts