Mean isoperimetry with control on outliers: exact and approximation algorithms

DOI10.1016/j.tcs.2022.05.022OpenAlexW3186958984WikidataQ114129102 ScholiaQ114129102MaRDI QIDQ2672637

Amir Daneshgar, Morteza Alimi, Mohammad-Hadi Foroughmand-Araabi

Publication date: 13 June 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.05125

zbMATH Keywords

connectivityisoperimetrygraph partitioningsparsest cut

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
• Multi-way dual Cheeger constants and spectral bounds of graphs
• On the complexity of isoperimetric problems on trees
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Sparsest cuts and bottlenecks in graphs
• Clustering and outlier detection using isoperimetric number of trees
• On the isoperimetric spectrum of graphs and its approximations
• Eigenvalues and expanders
• Minimum multiway cuts in trees
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Which problems have strongly exponential complexity?
• The geometry of graphs and some of its algorithmic applications
• Multi-way sparsest cut problem on trees with a control on the number of parts and outliers
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• On the hardness of approximating Multicut and Sparsest-Cut
• Potential theory for Schrödinger operators on finite networks
• Isoperimetric numbers of graphs
• Improved Guarantees for Tree Cut Sparsifiers
• Integrality gaps for sparsest cut and minimum linear arrangement problems
• $O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
• L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• LP Relaxation and Tree Packing for Minimum $k$-Cut
• Expander graphs and their applications
• Algorithmic Aspects of Graph Connectivity
• The Complexity of Multiterminal Cuts
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Community Detection and Stochastic Block Models
• Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
• Introduction to Analysis on Graphs
• EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS
• Cheeger-Type Approximation for Sparsest st -Cut
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Approximation Algorithm for Sparsest k-Partitioning
• Multi-way spectral partitioning and higher-order cheeger inequalities
• Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
• Euclidean distortion and the sparsest cut
• Improved Cheeger's inequality
• Sparsest cut on bounded treewidth graphs
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
• Expander flows, geometric embeddings and graph partitioning
• Improving the integrality gap for multiway cut
• On the complexity of \(k\)-SAT

This page was built for publication: Mean isoperimetry with control on outliers: exact and approximation algorithms