Cover Image

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Menand, Nicolas, Waingarten, Erik
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Average-Distortion Sketching
by: Bao, Yiqiao, et al.
Published: (2024)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
by: Khanna, Sanjeev, et al.
Published: (2025)

Streaming Max-Cut in General Metrics
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Streaming Graph Algorithms in the Massively Parallel Computation Model
by: Czumaj, Artur, et al.
Published: (2025)

Data-Dependent LSH for the Earth Mover's Distance
by: Jayaram, Rajesh, et al.
Published: (2024)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
by: Charikar, Moses, et al.
Published: (2024)

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
by: Gao, Jie, et al.
Published: (2025)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
by: Saxena, Raghuvansh R., et al.
Published: (2024)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Nearly Tight Bounds on Testing of Metric Properties
by: Bao, Yiqiao, et al.
Published: (2024)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
by: Mitrović, Slobodan, et al.
Published: (2025)

Max-Cut with Multiple Cardinality Constraints
by: Makarychev, Yury, et al.
Published: (2025)

Local Max-Cut on Sparse Graphs
by: Schwartzman, Gregory
Published: (2023)

Instance-Optimal Uniformity Testing and Tracking
by: Blanc, Guy, et al.
Published: (2025)

Max Cut with Small-Dimensional SDP Solutions
by: Chang, Hsien-Chih, et al.
Published: (2026)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Parallel Algorithm For Finding The Minimum s/t Cut in a Structured 3-Dimensional Proper Order Graph
by: Chandramouli, Shridharan
Published: (2026)

Distributed Algorithms for Euclidean Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
by: Beretta, Lorenzo, et al.
Published: (2025)

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

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
by: Anand, Aditya, et al.
Published: (2024)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
by: Alipour, Sharareh, et al.
Published: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms
by: Shi, Haoyan, et al.
Published: (2024)

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

Prune, Don't Rebuild: Efficiently Tuning $α$-Reachable Graphs for Nearest Neighbor Search
by: Zhang, Tian, et al.
Published: (2026)

Space Complexity of Minimum Cut Problems in Single-Pass Streams
by: Ding, Matthew, et al.
Published: (2024)

Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More
by: Stoian, Mihail
Published: (2026)

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

Tree Embedding in High Dimensions: Dynamic and Massively Parallel
by: Goranci, Gramoz, et al.
Published: (2025)

iFlow: An Interactive Max-Flow/Min-Cut Algorithms Visualizer
by: Ye, Muyang, et al.
Published: (2024)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
by: Gomes, Guilherme C. M., et al.
Published: (2024)

A Simple and Fast Algorithm for Fair Cuts
by: Li, Jason, et al.
Published: (2024)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
by: Azarmehr, Amir, et al.
Published: (2024)

Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering
by: Cao, Nairen, et al.
Published: (2024)

Streaming Algorithms for Network Design
by: Chekuri, Chandra, et al.
Published: (2025)

Streaming Algorithms for Connectivity Augmentation
by: Jin, Ce, et al.
Published: (2024)

Algorithms for Massive Data -- Lecture Notes
by: Prezza, Nicola
Published: (2023)

No Quantum Advantage in Decoded Quantum Interferometry for MaxCut
by: Parekh, Ojas
Published: (2025)