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...
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Dokumenttyp: | Article (Journal) Kapitel/Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
16 Dec 2021
|
| Ausgabe: | Version v2 |
| In: |
Arxiv
Year: 2021, Pages: 1-19 |
| DOI: | 10.48550/arXiv.2110.02750 |
| Online-Zugang: | Verlag, kostenfrei, Volltext: https://doi.org/10.48550/arXiv.2110.02750 Verlag, kostenfrei, Volltext: http://arxiv.org/abs/2110.02750 
|
| Verfasserangaben: | Erik Jenner, Enrique Fita Sanmartín, Fred A. Hamprecht |
| Zusammenfassung: | 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. ... |
|---|---|
| Beschreibung: | Online veröffentlicht am 5. Oktober 2021 Gesehen am 10.01.2024 |
| Beschreibung: | Online Resource |
| DOI: | 10.48550/arXiv.2110.02750 |