Cover Image

Streaming Max-Cut in General Metrics

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jiang, Shaofeng H. -C., Peng, Pan, Wang, Haoze
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

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
by: Menand, Nicolas, et al.
Published: (2025)

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

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

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

Coresets for Robust Clustering via Black-box Reductions to Vanilla Case
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

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

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

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

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

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

Round-efficient Fully-scalable MPC algorithms for k-Means
by: Jiang, Shaofeng H. -C., et al.
Published: (2026)

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

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

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

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

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

Local Search for Clustering in Almost-linear Time
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

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

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

Fitting Tree Metrics and Ultrametrics in Data Streams
by: Carmel, Amir, et al.
Published: (2025)

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
by: Dong, Yinhao, et al.
Published: (2024)

Near-Optimal Four-Cycle Counting in Graph Streams
by: Lüderssen, Sebastian, et al.
Published: (2026)

Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
by: Mo, Guanlin, et al.
Published: (2024)

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

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2026)

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

Min-Max Connected Multiway Cut
by: Tiwary, Hans Raj, et al.
Published: (2026)

Fair Clustering in the Sliding Window Model
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Learning-Augmented Streaming Algorithms for Correlation Clustering
by: Dong, Yinhao, et al.
Published: (2025)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
by: Michel, Lukas, et al.
Published: (2023)

Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts
by: Peng, Pan, et al.
Published: (2025)

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

Fully Dynamic Euclidean k-Means
by: Bhattacharya, Sayan, et al.
Published: (2025)

Relative Error Fair Clustering in the Weak-Strong Oracle Model
by: Braverman, Vladimir, et al.
Published: (2025)

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)

New Oracles and Labeling Schemes for Vertex Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
by: Jiang, Yonggang, et al.
Published: (2025)

Max-Cut with $ε$-Accurate Predictions
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Fully Dynamic Algorithms for Chamfer Distance
by: Goranci, Gramoz, et al.
Published: (2025)

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