Local Guarantees in Graph Cuts and Clustering

Moses Charikar, Neha Gupta, Roy Schwartz

Type: Book-Chapter

Publication Date: 2017-01-01

Citations: 18

DOI: https://doi.org/10.1007/978-3-319-59250-3_12

View Publication

Download PDF

Locations

Lecture notes in computer science - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Local Guarantees in Graph Cuts and Clustering	2017	Moses Charikar Neha Gupta Roy Schwartz
+ PDF Chat	Local approximation of the Maximum Cut in regular graphs	2020	Étienne Bamas Louis Esperet
+ PDF Chat	Local Approximation of the Maximum Cut in Regular Graphs	2019	Étienne Bamas Louis Esperet
+	Optimal cuts in graphs and statistical mechanics	1997	J C Anglès d'Auriac Myriam Preissmann András Sebö
+	On the number of small cuts in a graph	1996	Monika Henzinger David P. Williamson
+ PDF Chat	Graph Clustering with Surprise: Complexity and Exact Solutions	2014	Tobias Fleck Andrea Kappes Dorothea Wagner
+ PDF Chat	Criterions for locally dense subgraphs	2011	Gergely Tibély
+ PDF Chat	Local Balance in Graph Decompositions	2022	Flora C. Bowditch Peter J. Dukes
+	A Survey of Clustering Analysis and Clustering Analysis in Graphs	2018	Raven Da'Mon Gilmore
+ PDF Chat	Local Algorithms for Sparse Spanning Graphs	2019	Reut Levi Dana Ron Ronitt Rubinfeld
+	Decomposition algorithms for detecting low-diameter clusters in graphs	2016	Esmaeel Moradi
+	Clustering and Structural Balance in Graphs	1977	James A. Davis
+	Regularity lemmas for clustering graphs	2019	Fan Chung
+	Minimum cuts in parametric networks	1994	F. A. Sharifov
+ PDF Chat	Hypergraph cuts above the average	2019	David Conlon Jacob Fox Matthew Kwan Benny Sudakov
+	On finding the K best cuts in a network	1984	Horst W. Hamacher Jean‐Claude Picard Maurice Queyranne
+ PDF Chat	Exact and approximation methods by clique partition of graphs	2013	Raksmey Phan
+	Local spanning trees in graphs and hypergraph decomposition with respect to edge connectivity	2000	M KRIESELL
+	Local spanning trees in graphs and hypergraph decomposition with respect to edge connectivity	1999	Matthias Kriesell
+ PDF Chat	Graph clustering via generalized colorings	2022	András London Ryan R. Martin András Pluhár

Works That Cite This (12)

Action	Title	Year	Authors
+	Correlation Clustering and Biclustering With Locally Bounded Errors	2018	Gregory J. Puleo Olgica Milenković
+	Min-Max Correlation Clustering via MultiCut.	2019	Saba Ahmadi Sainyam Galhotra Samir Khuller Barna Saha Roy Schwartz
+ PDF Chat	Fixed Parameter Approximation Scheme for Min-Max k-Cut	2021	Karthekeyan Chandrasekaran Weihang Wang
+ PDF Chat	Efficient enumeration of the optimal solutions to the correlation clustering problem	2023	Nejat Arınık Rosa Figueiredo Vincent Labatut
+ PDF Chat	Fixed parameter approximation scheme for min-max k-cut	2022	Karthekeyan Chandrasekaran Weihang Wang
+ PDF Chat	Correlation Clustering with Sherali-Adams	2022	Vincent Cohen-Addad Euiwoong Lee Alantha Newman
+	Local Correlation Clustering with Asymmetric Classification Errors	2021	Jafar Jafarov Sanchit Kalhan Konstantin Makarychev Yury Makarychev
+	Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering	2020	Vaggos Chatziafratis Neha Gupta Euiwoong Lee
+ PDF Chat	Min-Max Correlation Clustering via MultiCut	2019	Saba Ahmadi Samir Khuller Barna Saha
+	Improved algorithms for Correlation Clustering with local objectives	2019	Sanchit Kalhan Konstantin Makarychev Timothy Zhou

Works Cited by This (1)

Action	Title	Year	Authors
+ PDF Chat	Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs	2015	Shuchi Chawla Konstantin Makarychev Tselil Schramm Grigory Yaroslavtsev