Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction

DOI10.1145/3564246.3585170MaRDI QIDQ6499222zbMATH OpenFDO

Authors Xiao-Yu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer

Publication date 8 May 2024

Full work available at URL https://doi.org/10.1145/3564246.3585170

zbMATH Keywords

data reductiondimension reductionmax cutstreaming

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• 1-pass relative-error L_p-sampling with applications
• (1 + )-approximation for facility location in data streams
• A randomized approximation scheme for metric MAX-CUT
• A unified framework for approximating and clustering data
• Algorithms for dynamic geometric problems over data streams
• An almost space-optimal streaming algorithm for coresets in fixed dimensions
• An optimal space lower bound for approximating MAX-CUT
• Approximating extent measures of points.
• Clustering for edge-cost minimization (extended abstract)
• Communication Complexity
• Coresets in dynamic geometric data streams
• Efficient Sketches for Earth-Mover Distance, with Applications
• Extensions of Lipschitz mappings into a Hilbert space
• Facility Location in Dynamic Geometric Data Streams
• Graph Sparsification in the Semi-streaming Model
• scientific article; zbMATH DE number 1496577 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Non-adaptive adaptive sampling on turnstile streams
• On coresets for k-means and k-median clustering
• On randomized one-round communication complexity
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Perfect \(L_p\) sampling in a data stream
• Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Property testing and its connection to learning and approximation
• Random sampling and approximation of MAX-CSPs
• Sampling from large matrices
• SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS
• Streaming algorithms for extent problems in high dimensions
• Streaming Embeddings with Slack
• The one-way communication complexity of Hamming distance
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering

Cited in

(5)

• Space complexity of Euclidean clustering
• Moderate dimension reduction for k-center clustering
• Streaming algorithms for geometric Steiner forest
• Dynamic streaming algorithms for geometric independent set
• Streaming diameter of high-dimensional points

This page was built for publication: Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499222)