Extensions of Karger's algorithm: why they fail in theory and how they are useful in practice
The minimum graph cut and minimum s-t-cut problems are important primitives in the modeling of combinatorial problems in computer science, including in computer vision and machine learning. Some of the most efficient algorithms for finding global minimum cuts are randomized algorithms based on Karge...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article (Journal) Chapter/Article |
| Language: | English |
| Published: |
16 Dec 2021
|
| Edition: | Version v2 |
| In: |
Arxiv
Year: 2021, Pages: 1-19 |
| DOI: | 10.48550/arXiv.2110.02750 |
| Online Access: | Verlag, kostenfrei, Volltext: https://doi.org/10.48550/arXiv.2110.02750 Verlag, kostenfrei, Volltext: http://arxiv.org/abs/2110.02750 
|
| Author Notes: | Erik Jenner, Enrique Fita Sanmartín, Fred A. Hamprecht |
| Summary: | The minimum graph cut and minimum s-t-cut problems are important primitives in the modeling of combinatorial problems in computer science, including in computer vision and machine learning. Some of the most efficient algorithms for finding global minimum cuts are randomized algorithms based on Karger’s groundbreaking contraction algorithm. Here, we study whether Karger’s algorithm can be successfully generalized to other cut problems. We first prove that a wide class of natural generalizations of Karger’s algorithm cannot efficiently solve the s-t-mincut or the normalized cut problem to optimality. However, we then present a simple new algorithm for seeded segmentation / graph-based semisupervised learning that is closely based on Karger’s original algorithm, showing that for these problems, extensions of Karger’s algorithm can be useful. ... |
|---|---|
| Item Description: | Online veröffentlicht am 5. Oktober 2021 Gesehen am 10.01.2024 |
| Physical Description: | Online Resource |
| DOI: | 10.48550/arXiv.2110.02750 |