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 |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 181834968X | ||
| 003 | DE-627 | ||
| 005 | 20240110133805.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 221010s2021 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.48550/arXiv.2110.02750 |2 doi | |
| 035 | |a (DE-627)181834968X | ||
| 035 | |a (DE-599)KXP181834968X | ||
| 035 | |a (OCoLC)1361713944 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Jenner, Erik |e VerfasserIn |0 (DE-588)1315529998 |0 (DE-627)1877647756 |4 aut | |
| 245 | 1 | 0 | |a Extensions of Karger's algorithm |b why they fail in theory and how they are useful in practice |c Erik Jenner, Enrique Fita Sanmartín, Fred A. Hamprecht |
| 246 | 3 | 0 | |a Karger |
| 250 | |a Version v2 | ||
| 264 | 1 | |c 16 Dec 2021 | |
| 300 | |b Illustrationen | ||
| 300 | |a 19 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Online veröffentlicht am 5. Oktober 2021 | ||
| 500 | |a Gesehen am 10.01.2024 | ||
| 520 | |a 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. ... | ||
| 650 | 4 | |a Computer Science - Computer Vision and Pattern Recognition | |
| 650 | 4 | |a Computer Science - Data Structures and Algorithms | |
| 650 | 4 | |a Computer Science - Machine Learning | |
| 650 | 4 | |a Statistics - Machine Learning | |
| 700 | 1 | |a Fita Sanmartín, Enrique |d 1994- |e VerfasserIn |0 (DE-588)1262514363 |0 (DE-627)1810211522 |4 aut | |
| 700 | 1 | |a Hamprecht, Fred |e VerfasserIn |0 (DE-588)1020505605 |0 (DE-627)691240280 |0 (DE-576)360605516 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Arxiv |d Ithaca, NY : Cornell University, 1991 |g (2021), Artikel-ID 2110.02750, Seite 1-19 |h Online-Ressource |w (DE-627)509006531 |w (DE-600)2225896-6 |w (DE-576)28130436X |7 nnas |a Extensions of Karger's algorithm why they fail in theory and how they are useful in practice |
| 773 | 1 | 8 | |g year:2021 |g elocationid:2110.02750 |g pages:1-19 |g extent:19 |a Extensions of Karger's algorithm why they fail in theory and how they are useful in practice |
| 856 | 4 | 0 | |u https://doi.org/10.48550/arXiv.2110.02750 |x Verlag |x Resolving-System |z kostenfrei |3 Volltext |
| 856 | 4 | 0 | |u http://arxiv.org/abs/2110.02750 |x Verlag |z kostenfrei |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20221010 | ||
| 993 | |a Article | ||
| 994 | |a 2021 | ||
| 998 | |g 1020505605 |a Hamprecht, Fred |m 1020505605:Hamprecht, Fred |d 700000 |d 708070 |d 700000 |d 728500 |e 700000PH1020505605 |e 708070PH1020505605 |e 700000PH1020505605 |e 728500PH1020505605 |k 0/700000/ |k 1/700000/708070/ |k 0/700000/ |k 1/700000/728500/ |p 3 |y j | ||
| 998 | |g 1262514363 |a Fita Sanmartín, Enrique |m 1262514363:Fita Sanmartín, Enrique |d 700000 |d 728500 |e 700000PF1262514363 |e 728500PF1262514363 |k 0/700000/ |k 1/700000/728500/ |p 2 | ||
| 999 | |a KXP-PPN181834968X |e 4195519918 | ||
| BIB | |a Y | ||
| JSO | |a {"person":[{"display":"Jenner, Erik","family":"Jenner","role":"aut","given":"Erik"},{"family":"Fita Sanmartín","display":"Fita Sanmartín, Enrique","role":"aut","given":"Enrique"},{"role":"aut","given":"Fred","family":"Hamprecht","display":"Hamprecht, Fred"}],"language":["eng"],"note":["Online veröffentlicht am 5. Oktober 2021","Gesehen am 10.01.2024"],"title":[{"title":"Extensions of Karger's algorithm","subtitle":"why they fail in theory and how they are useful in practice","title_sort":"Extensions of Karger's algorithm"}],"origin":[{"dateIssuedDisp":"16 Dec 2021","edition":"Version v2","dateIssuedKey":"2021"}],"type":{"media":"Online-Ressource","bibl":"chapter"},"recId":"181834968X","physDesc":[{"extent":"19 S.","noteIll":"Illustrationen"}],"name":{"displayForm":["Erik Jenner, Enrique Fita Sanmartín, Fred A. Hamprecht"]},"id":{"eki":["181834968X"],"doi":["10.48550/arXiv.2110.02750"]},"relHost":[{"disp":"Extensions of Karger's algorithm why they fail in theory and how they are useful in practiceArxiv","language":["eng"],"part":{"text":"(2021), Artikel-ID 2110.02750, Seite 1-19","pages":"1-19","year":"2021","extent":"19"},"origin":[{"publisherPlace":"Ithaca, NY ; [Erscheinungsort nicht ermittelbar]","dateIssuedDisp":"1991-","dateIssuedKey":"1991","publisher":"Cornell University ; Arxiv.org"}],"note":["Gesehen am 28.05.2024"],"titleAlt":[{"title":"Arxiv.org"},{"title":"Arxiv.org e-print archive"},{"title":"Arxiv e-print archive"},{"title":"De.arxiv.org"}],"title":[{"title":"Arxiv","title_sort":"Arxiv"}],"type":{"bibl":"edited-book","media":"Online-Ressource"},"recId":"509006531","pubHistory":["1991 -"],"physDesc":[{"extent":"Online-Ressource"}],"id":{"zdb":["2225896-6"],"eki":["509006531"]}}]} | ||
| SRT | |a JENNERERIKEXTENSIONS1620 | ||