Cheeger Inequalities for Submodular Transformations

DOI10.1137/1.9781611975482.160zbMath1434.05096arXiv1708.08781OpenAlexW2753289174MaRDI QIDQ5236350

Yuichi Yoshida

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

spectral graph theorysubmodular transformation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (12)

Core-Periphery Detection in Hypergraphs ⋮ Measured continuous greedy with differential privacy ⋮ A new transport distance and its associated Ricci curvature of hypergraphs ⋮ Unnamed Item ⋮ Finding Cheeger cuts in hypergraphs via heat equation ⋮ Generalizing \(p\)-Laplacian: spectral hypergraph theory and a partitioning algorithm ⋮ Geometric and spectral properties of directed graphs under a lower Ricci curvature bound ⋮ Cheng's maximal diameter theorem for hypergraphs ⋮ Nonlinear evolution equation associated with hypergraph Laplacian ⋮ Polynomial-time algorithms for submodular Laplacian systems ⋮ Diffusion operator and spectral analysis for directed hypergraph Laplacian ⋮ Private non-monotone submodular maximization

This page was built for publication: Cheeger Inequalities for Submodular Transformations