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 recent years, hypergraph generalizations of many graph cut problems havebeen introduced and analyzed as a way to better explore and understand complexsystems and datasets characterized by multiway relationships. Recent work hasmade use of a generalized hypergraph cut function which for a hypergraph$\mathcal{H} = (V,E)$ can be defined by associating each hyperedge $e \in E$with a splitting function ${\bf w}_e$, which assigns a penalty to each way ofseparating the nodes of $e$. When each ${\bf w}_e$ is a submodularcardinality-based splitting function, meaning that ${\bf w}_e(S) = g(|S|)$ forsome concave function $g$, previous work has shown that a generalizedhypergraph cut problem can be reduced to a directed graph cut problem on anaugmented node set. However, existing reduction procedures often result in adense graph, even when the hypergraph is sparse, which leads to slow runtimesfor algorithms that run on the reduced graph.  We introduce a new framework of sparsifying hypergraph-to-graph reductions,where a hypergraph cut defined by submodular cardinality-based splittingfunctions is $(1+\varepsilon)$-approximated by a cut on a directed graph. Ourtechniques are based on approximating concave functions using piecewise linearcurves. For $\varepsilon > 0$ we need at most $O(\varepsilon^{-1}|e| \log |e|)$edges to reduce any hyperedge $e$, which leads to faster runtimes forapproximating generalized hypergraph $s$-$t$ cut problems. For the machinelearning heuristic of a clique splitting function, our approach requires only$O(|e| \varepsilon^{-1/2} \log \log \frac{1}{\varepsilon})$ edges. Thissparsification leads to faster approximate min $s$-$t$ graph cut algorithms forcertain classes of co-occurrence graphs. Finally, we apply our sparsificationtechniques to develop approximation algorithms for minimizing sums ofcardinality-based submodular functions.

Augmented Sparsifiers for Generalized Hypergraph Cuts with Applications to Decomposable Submodular Function Minimization