Copertina

Sketching Cuts in Graphs and Hypergraphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Kogan, Dmitry, Krauthgamer, Robert
Natura:	Preprint
Pubblicazione:	2014
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Cut Sparsification and Succinct Representation of Submodular Hypergraphs
di: Kenneth, Yotam, et al.
Pubblicazione: (2023)

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
di: Kenneth-Mordoch, Yotam, et al.
Pubblicazione: (2025)

Cut-Query Algorithms with Few Rounds
di: Kenneth-Mordoch, Yotam, et al.
Pubblicazione: (2025)

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
di: Kenneth-Mordoch, Yotam, et al.
Pubblicazione: (2025)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
di: Khanna, Sanjeev, et al.
Pubblicazione: (2024)

On Sketching Quadratic Forms
di: Andoni, Alexandr, et al.
Pubblicazione: (2015)

Stable coresets: Unleashing the power of uniform sampling
di: Carmel, Amir, et al.
Pubblicazione: (2025)

Simple Algorithms for Fully Dynamic Edge Connectivity
di: Kenneth-Mordoch, Yotam, et al.
Pubblicazione: (2025)

On Solving Linear Systems in Sublinear Time
di: Andoni, Alexandr, et al.
Pubblicazione: (2018)

Near-Optimal Minimum Cuts in Hypergraphs at Scale
di: Chhabra, Adil, et al.
Pubblicazione: (2025)

Moderate Dimension Reduction for $k$-Center Clustering
di: Jiang, Shaofeng H. -C., et al.
Pubblicazione: (2023)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
di: Khanna, Sanjeev, et al.
Pubblicazione: (2025)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
di: Khanna, Sanjeev, et al.
Pubblicazione: (2024)

The Case for External Graph Sketching
di: Bender, Michael A., et al.
Pubblicazione: (2025)

Coresets for Kernel Clustering
di: Jiang, Shaofeng H. -C., et al.
Pubblicazione: (2021)

Near-Optimal Dimension Reduction for Facility Location
di: Huang, Lingxiao, et al.
Pubblicazione: (2024)

Streaming Algorithms for Geometric Steiner Forest
di: Czumaj, Artur, et al.
Pubblicazione: (2020)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
di: Krauthgamer, Robert, et al.
Pubblicazione: (2026)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
di: Jiang, Shaofeng H. -C., et al.
Pubblicazione: (2025)

Clustering Permutations: New Techniques with Streaming Applications
di: Chakraborty, Diptarka, et al.
Pubblicazione: (2022)

Local Max-Cut on Sparse Graphs
di: Schwartzman, Gregory
Pubblicazione: (2023)

New Graph and Hypergraph Container Lemmas with Applications in Property Testing
di: Blais, Eric, et al.
Pubblicazione: (2024)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
di: Adriaens, Florian, et al.
Pubblicazione: (2024)

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
di: Zhao, Yibin
Pubblicazione: (2025)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
di: Ghoshal, Suprovat, et al.
Pubblicazione: (2026)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2025)

The Power of Recursive Embeddings for $\ell_p$ Metrics
di: Krauthgamer, Robert, et al.
Pubblicazione: (2025)

Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
di: De Man, Quinten, et al.
Pubblicazione: (2026)

On Sketching Trimmed Statistics
di: Lin, Honghao, et al.
Pubblicazione: (2025)

Average-Distortion Sketching
di: Bao, Yiqiao, et al.
Pubblicazione: (2024)

Fast Similarity Sketching
di: Dahlgaard, Søren, et al.
Pubblicazione: (2017)

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
di: Mallek, Nadym, et al.
Pubblicazione: (2025)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
di: Ahi, Mridul, et al.
Pubblicazione: (2025)

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
di: Chen, Yu, et al.
Pubblicazione: (2024)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
di: Henzinger, Monika, et al.
Pubblicazione: (2024)

LMQ-Sketch: Lagom Multi-Query Sketch for High-Rate Online Analytics
di: Hilgendorf, Martin, et al.
Pubblicazione: (2025)

An Algorithmic Bridge Between Hamming and Levenshtein Distances
di: Goldenberg, Elazar, et al.
Pubblicazione: (2022)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
di: Jiang, Yonggang, et al.
Pubblicazione: (2025)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
di: Chalermsook, Parinya, et al.
Pubblicazione: (2021)