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 minimum graph cut and minimum $s$-$t$-cut problems are importantprimitives in the modeling of combinatorial problems in computer science,including in computer vision and machine learning. Some of the most efficientalgorithms for finding global minimum cuts are randomized algorithms based onKarger's groundbreaking contraction algorithm. Here, we study whether Karger'salgorithm can be successfully generalized to other cut problems. We first provethat a wide class of natural generalizations of Karger's algorithm cannotefficiently solve the $s$-$t$-mincut or the normalized cut problem tooptimality. However, we then present a simple new algorithm for seededsegmentation / graph-based semi-supervised learning that is closely based onKarger's original algorithm, showing that for these problems, extensions ofKarger's algorithm can be useful. The new algorithm has linear asymptoticruntime and yields a potential that can be interpreted as the posteriorprobability of a sample belonging to a given seed / class. We clarify itsrelation to the random walker algorithm / harmonic energy minimization in termsof distributions over spanning forests. On classical problems from seeded imagesegmentation and graph-based semi-supervised learning on image data, the methodperforms at least as well as the random walker / harmonic energy minimization /Gaussian processes.

Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practice