Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912281530466304 |
|---|---|
| author | Menand, Nicolas Waingarten, Erik |
| author_facet | Menand, Nicolas Waingarten, Erik |
| contents | Given a set of vectors $X = \{ x_1,\dots, x_n \} \subset \mathbb{R}^d$, the Euclidean max-cut problem asks to partition the vectors into two parts so as to maximize the sum of Euclidean distances which cross the partition. We design new algorithms for Euclidean max-cut in models for massive datasets:
$\bullet$ We give a fully-scalable constant-round MPC algorithm using $O(nd) + n \cdot \text{poly}( \log(n) / ε)$ total space which gives a $(1+ε)$-approximate Euclidean max-cut.
$\bullet$ We give a dynamic streaming algorithm using $\text{poly}(d \log Δ/ ε)$ space when $X \subseteq [Δ]^d$, which provides oracle access to a $(1+ε)$-approximate Euclidean max-cut.
Recently, Chen, Jiang, and Krauthgamer $[\text{STOC}~'23]$ gave a dynamic streaming algorithm with space $\text{poly}(d\logΔ/ε)$ to approximate the value of the Euclidean max-cut, but could not provide oracle access to an approximately optimal cut. This was left open in that work, and we resolve it here. Both algorithms follow from the same framework, which analyzes a ``parallel'' and ``subsampled'' (Euclidean) version of a greedy algorithm of Mathieu and Schudy $[\text{SODA}~'08]$ for dense max-cut. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_14362 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Streaming and Massively Parallel Algorithms for Euclidean Max-Cut Menand, Nicolas Waingarten, Erik Data Structures and Algorithms Given a set of vectors $X = \{ x_1,\dots, x_n \} \subset \mathbb{R}^d$, the Euclidean max-cut problem asks to partition the vectors into two parts so as to maximize the sum of Euclidean distances which cross the partition. We design new algorithms for Euclidean max-cut in models for massive datasets: $\bullet$ We give a fully-scalable constant-round MPC algorithm using $O(nd) + n \cdot \text{poly}( \log(n) / ε)$ total space which gives a $(1+ε)$-approximate Euclidean max-cut. $\bullet$ We give a dynamic streaming algorithm using $\text{poly}(d \log Δ/ ε)$ space when $X \subseteq [Δ]^d$, which provides oracle access to a $(1+ε)$-approximate Euclidean max-cut. Recently, Chen, Jiang, and Krauthgamer $[\text{STOC}~'23]$ gave a dynamic streaming algorithm with space $\text{poly}(d\logΔ/ε)$ to approximate the value of the Euclidean max-cut, but could not provide oracle access to an approximately optimal cut. This was left open in that work, and we resolve it here. Both algorithms follow from the same framework, which analyzes a ``parallel'' and ``subsampled'' (Euclidean) version of a greedy algorithm of Mathieu and Schudy $[\text{SODA}~'08]$ for dense max-cut. |
| title | Streaming and Massively Parallel Algorithms for Euclidean Max-Cut |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.14362 |