Extensions of Karger's algorithm

• Verfasst von: Jenner, Erik [VerfasserIn]
• Verfasst von: Fita Sanmartín, Enrique [VerfasserIn]
• Verfasst von: Hamprecht, Fred [VerfasserIn]
• Titel: Extensions of Karger's algorithm
• Titelzusatz: why they fail in theory and how they are useful in practice
• Verf.angabe: Erik Jenner, Enrique Fita Sanmartín, Fred A. Hamprecht
• Ausgabe: Version v2
• E-Jahr: 2021
• Jahr: 16 Dec 2021
• Umfang: 19 S.
• Illustrationen: Illustrationen
• Fussnoten: Online veröffentlicht am 5. Oktober 2021 ; Gesehen am 10.01.2024
• Titel Quelle: Enthalten in: De.arxiv.org
• Ort Quelle: [Erscheinungsort nicht ermittelbar] : Arxiv.org, 1991
• Jahr Quelle: 2021
• Band/Heft Quelle: (2021), Artikel-ID 2110.02750, Seite 1-19
• DOI: doi:10.48550/arXiv.2110.02750
• Datenträger: Online-Ressource
• Sprache: eng
• Sach-SW: Computer Science - Computer Vision and Pattern Recognition
• Sach-SW: Computer Science - Data Structures and Algorithms
• Sach-SW: Computer Science - Machine Learning
• Sach-SW: Statistics - Machine Learning
• K10plus-PPN: 181834968X

Abstract

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. ...