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

For an edge-weighted connected undirected graph, the minimum k-way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into k connected components. The problem is NP-hard when k is part of the input and W[1]-hard when k is taken as a parameter.   A simple algorithm for approximating a minimum k-way cut is to iteratively increase the number of components of the graph by h−1, where 2≤h≤k, until the graph has k components. The approximation ratio of this algorithm is known for h≤3 but is open for h≥4.    In this paper, we consider a general algorithm that successively increases the number of components of the graph by h  i −1, where 2≤h 1≤h 2≤⋅⋅⋅≤h  q  and ∑ i=1 q (h  i −1)=k−1. We prove that the approximation ratio of this general algorithm is   , which is tight. Our result implies that the approximation ratio of the simple iterative algorithm is 2−h/k+O(h 2/k 2) in general and 2−h/k if k−1 is a multiple of h−1.

Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem