Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction
From MaRDI portal
Publication:6499222
DOI10.1145/3564246.3585170MaRDI QIDQ6499222
Xiao-yu Chen, Robert Krauthgamer, Shaofeng H.-C. Jiang
Publication date: 8 May 2024
Could not fetch data.
Cites Work
- An almost space-optimal streaming algorithm for coresets in fixed dimensions
- On randomized one-round communication complexity
- A randomized approximation scheme for metric MAX-CUT
- Random sampling and approximation of MAX-CSPs
- Streaming algorithms for extent problems in high dimensions
- Approximating extent measures of points
- Property testing and its connection to learning and approximation
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Streaming Embeddings with Slack
- Clustering for edge-cost minimization (extended abstract)
- Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
- Extensions of Lipschitz mappings into a Hilbert space
- SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS
- Facility Location in Dynamic Geometric Data Streams
- Sampling from large matrices
- On coresets for k-means and k-median clustering
- Algorithms for dynamic geometric problems over data streams
- Coresets in dynamic geometric data streams
- Graph Sparsification in the Semi-streaming Model
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Communication Complexity
- Non-adaptive adaptive sampling on turnstile streams
- Efficient Sketches for Earth-Mover Distance, with Applications
- An optimal space lower bound for approximating MAX-CUT
- Performance of Johnson-Lindenstrauss transform for k -means and k -medians clustering
- A unified framework for approximating and clustering data
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- (1 + ε)-Approximation for Facility Location in Data Streams
- Perfect $L_p$ Sampling in a Data Stream
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction