Source-linked AI summary
Parallel Algorithms for Geometric Graph Problems
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev
TL;DR
The paper addresses how to design efficient parallel algorithms for geometric graph problems when analogous general-graph problems remain difficult. It proposes the Solve-and-Sketch framework and applies it to MST, EMD, and transportation cost, obtaining approximate solutions in few communication rounds and consequences beyond the parallel model. The results include geometric MST and planar EMD algorithms, plus streaming-with-sorting implications, while optimality and black-box query limitations remain open or constrained.
Problem
New algorithmic ideas are needed for MapReduce-like models, where sparse general-graph connectivity remains difficult and 1+ϵ streaming approximation for EMD is open.
Method
The paper proposes the Solve-and-Sketch framework for geometric graph problems and implements it in the MPC model.
Results
The framework achieves 1+ϵ approximation in a constant number of rounds for geometric MST and applies to EMD and transportation cost.
Takeaways & Limitations
Geometric representations can enable parallel speedups, while the framework also yields near-linear-time planar EMD and streaming-with-sorting consequences.
Takeaways & Limitations
Optimality is unresolved, and the lower-bound results concern the black-box distance-query model for bounded-doubling-dimension MST.
Abstract
from arXiv · showhide
We give algorithms for geometric graph problems in the modern parallel models inspired by MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points in the two-dimensional space, our algorithm computes a $(1+ε)$-approximate MST. Our algorithms work in a constant number of rounds of communication, while using total space and communication proportional to the size of the data (linear space and near linear time algorithms). In contrast, for general graphs, achieving the same result for MST (or even connectivity) remains a challenging open problem, despite drawing significant attention in recent years. We develop a general algorithmic framework that, besides MST, also applies to Earth-Mover Distance (EMD) and the transportation cost problem. Our algorithmic framework has implications beyond the MapReduce model. For example it yields a new algorithm for computing EMD cost in the plane in near-linear time, $n^{1+o_ε(1)}$. We note that while recently Sharathkumar and Agarwal developed a near-linear time algorithm for $(1+ε)$-approximating EMD, our algorithm is fundamentally different, and, for example, also solves the transportation (cost) problem, raised as an open question in their work. Furthermore, our algorithm immediately gives a $(1+ε)$-approximation algorithm with $n^δ$ space in the streaming-with-sorting model with $1/δ^{O(1)}$ passes. As such, it is tempting to conjecture that the parallel models may also constitute a concrete playground in the quest for efficient algorithms for EMD (and other similar problems) in the vanilla streaming model, a well-known open problem.
1 Introduction
The paper develops geometric graph algorithms for MapReduce-like parallel models, achieving constant-round approximations where general-graph problems remain difficult. Its Solve-and-Sketch framework applies to MST and EMD, with consequences for near-linear-time and streaming-with-sorting algorithms.
- Motivation: The paper asks what models and algorithmic ideas can support effective parallel computation beyond existing PRAM-based approaches.The discussion emphasizes MapReduce-like systems and the need for new algorithms tailored to their capabilities.
- Motivation: Connectivity in sparse general graphs remains a challenging challenge problem, with logarithmic lower bounds known for restricted algorithms.This motivates studying settings where geometric structure may enable faster algorithms.
- Contributions: 1 + ϵ approximation is achieved in a constant number of rounds for geometric MST and related graph problems through a common framework.The framework suggests geometric representations can enable speedups that are difficult for standard graph algorithms.
- Broader implications: The framework produces a near-linear-time planar EMD algorithm and a streaming-with-sorting algorithm using n^δ space and 1/δ^O(1) passes.The streaming consequence addresses a setting where 1+ϵ approximation for EMD is identified as an open question, though the broader streaming implication remains unresolved.
- Model: The paper studies algorithms in the MPC model, where total space is O(n), communication is round-bounded, and round complexity is the primary measure.Each machine has space s, and m·s = O(n).
- MST: O(log_s n) rounds compute a 1+ϵ approximate MST over R^d when (1/ϵ)^O(d) < s, with per-machine per-round time s^O(1)(1/ϵ)^O(d).The number of rounds does not depend on ϵ or d, and the algorithm outputs the actual tree in distributed form.
- EMD and streaming: (log n)^O(1) rounds approximate planar EMD and transportation cost within 1 + ϵ under the stated local-space condition.The framework also yields n^1+o(1) sequential time for fixed ϵ and n^δ space with 1/δ^O(1) passes in streaming-with-sorting.
- Contributions: The Solve-and-Sketch framework organizes the algorithms and is designed to remain naturally parallelizable across modest changes in the parallel model.Its MPC implementation is described separately from the general framework.
2 Preliminaries: Solve-And-Sketch Framework
Solve-And-Sketch separates geometric problem-solving from parallel implementation by recursively computing local solutions and sending compact sketches upward a hierarchical partition. A general theorem converts suitable unit-step algorithms into polylogarithmic-round MPC algorithms.
- Unit step: Solve-And-Sketch applies a unit step to each partition cell, processing leaf inputs and recursively combining children’s outputs at higher levels.The top-level cell’s output becomes the problem output, possibly after post-processing.
- Hierarchical implementation: The computation is organized bottom-up on a hierarchical partition, with parallel processing at each level and sketches passed between machines.The partition has arity at most √s and depth O(log_s n).
- Unit step: Each unit step solves for partial or potential solutions, sketches them within a bounded output size, and sends the representation to the parent.The sketch is intended to represent solutions in the current part using at most pu ≤√s space.
- Framework challenges: The framework’s central design challenge is choosing local solutions and sketches that preserve global optimality without requiring linear space.Naïve local choices may ignore information outside a part or fail to admit a sublinear representation.
- Framework guarantee: If a unit step has non-decreasing time, space, and output-size functions satisfying the stated MPC bounds, Solve-And-Sketch yields (log_s n)^O(1) rounds.The theorem requires su(pu(s)) ≤ s^1/3 and pu(s) ≤ s^1/3, with local runtime s · tu(s) · (log n)^O(1) per machine per round.
3 Minimum Spanning Tree
For points in constant-dimensional Euclidean space, the paper constructs a Solve-And-Sketch MST algorithm that outputs a near-optimal spanning tree in polylogarithmic rounds with near-linear local computation. The approach uses hierarchical metric partitions, local forest construction, coverings, and approximate intercomponent connections.
- Result: Theorem 3.1 gives a spanning tree within a 1 + ϵ factor of optimal in (log_s n)^O(1) MPC rounds.The result assumes s ≥ (ϵ^-1 log_s n)^O(1) and applies to constant-dimensional Euclidean distance.
- Complexity: The per-machine running time is O(nuϵ^-d log^O(1) nu), providing near-linear computation in the local input size.The unit-step bounds also give space nu log^O(1) nu words and output size O(ϵ^-d) in the Euclidean partition.
- Metric preliminaries: A metric space is represented by points S with distance function ρ, and the algorithm uses coverings, packings, nets, and doubling dimension to control geometric structure.The doubling dimension bounds how many half-radius balls cover any ball; restricted subspaces have doubling dimension at most 2d.
- Hierarchical partitions: The framework uses randomized hierarchical partitions of the metric space, with cells subdividing across levels and distance-preserving guarantees controlling approximation.A distance-preserving partition specifies cell diameters and bounds the probability that a pair is separated.
- Unit step: The SAS unit step recursively processes partition cells, computes local minimum spanning forests, and outputs sketches or coverings annotated by connected components.At later levels, an ϵ^2Δℓ-covering summarizes points while retaining component information for future connections.
- Approximation analysis: The analysis bounds the expected surrogate edge weight between ρ(u,v) and (1 + ϵLb)ρ(u,v), while local distance approximation differs by at most 2ϵ^2Δℓ−1.The proof relates each SAS edge to the corresponding Kruskal edge and to an approximately shortest non-crossing intercluster edge.
- Output and implementation: The algorithm outputs the actual tree, rather than only its cost, and the tree has size approximately n with distributed storage.Component colors change only logarithmically many times, supporting the stated total running-time and space bounds.
4 EMD and Transportation Problem Cost
The section develops parallel algorithms for approximating Euclidean Transportation cost and EMD, using a hierarchical grid metric, local cost-function sketches, and Solve-and-Sketch recursion. The framework yields polylogarithmic-round MPC algorithms, near-linear sequential algorithms, and streaming-with-sorting algorithms.
- Problem formulation: Transportation cost is minimum-cost flow between weighted point sets, while unit demands reduce it to Earth-Mover Distance.The Euclidean setting uses points in R2 and generalizes to any norm in fixed-dimensional Rd.
- Parallel results: The MPC algorithm uses (log n)O(1) rounds, polynomial local computation, and space parameter s satisfying s ≥ (log n)(ϵ−1 log s n)Ω(1), producing a 1+ϵ approximation.The result applies to polynomially bounded demands in the plane.
- Consequences: The framework also gives a near-linear sequential transportation algorithm and a streaming-with-sorting algorithm using nδ space and 1/δO(1) rounds.The transportation result answers an open problem identified in prior work.
- New distance: The grid metric ρg recursively routes distances through hierarchical partition nets, and approximates the Euclidean metric within 1+O(δL) with probability 9/10.The construction preserves an upper bound on the original metric through the triangle inequality.
- Cost-function sketches: The algorithm sketches local cost functions by exploiting lower bounds and Lipschitz continuity, obtaining multiplicative error at most ϵ with polylogarithmic sketch size.For δ = ϵO(1), each sketch has size (log n)1/ϵO(1).
- Solve-and-Sketch: The Solve-and-Sketch unit step computes an 1 ± O(Lϵ) approximation to transportation cost while producing output of size (log n)ϵ−O(1).The unit step is implemented using a flow formulation whose optimum equals the generalized cost function F.
5 Parallel Implementation of the Solve-And-Sketch Framework
The MPC implementation evaluates Solve-and-Sketch over a hierarchical partition by sorting unprocessed cells, assigning intervals to machines, and recursively applying unit steps. Boundary-cell bounds and shrinking outputs yield polylogarithmic rounds with controlled local space and computation.
- Framework implementation: The implementation labels points by a hierarchical partition and applies unit steps from child cells toward parent cells.A good ordering preserves the hierarchy and supports efficient cell comparisons.
- Boundary analysis: At most 2(c−1)L boundary cells occur for any interval of the partition ordering at each level.This structural bound limits the number of cells that remain active across machines.
- Framework implementation: Algorithm 2 repeatedly sorts eligible cells, assigns cell intervals to machines, and applies unit steps using child outputs as inputs.If an output exceeds its input, lazy evaluation retains the input instead.
- Round complexity: The general simulation theorem completes all unit steps in R·O(log_s n) rounds, with high probability, under space and output-size conditions on the unit step.Local computation is bounded using the cell-comparison time, partition depth, and unit-step time.
- Round complexity: The number of active cells shrinks by a factor of √s per round once the output-size condition holds, so completion takes O(log_s n) rounds after the corresponding stage.Each machine receives O(s) information, and lazy evaluation keeps total information bounded by O(n).
- Partition construction: A randomized distance-preserving hierarchical partition can be constructed and labeled in O(log_s n) MPC rounds, with cell comparisons taking O(dL) time.The framework applies to points in low-dimensional spaces under the stated partition guarantees.
6 Algorithms for Bounded Doubling Dimension
The section develops parallel algorithms for bounded-doubling-dimension metrics using sampled nets, hierarchical distance-preserving partitions, and approximate nearest-neighbor structures. These tools yield efficient approximate MST algorithms with bounded space, round, and per-machine computation guarantees.
- Net construction: A parallel algorithm computes a (δ, δ/4)-net with probability 1 − γ and size at most 3^d(n/m).Each machine uses O(n/m) space, with stated round and per-round computation bounds.
- Net construction: The efficient net algorithm replaces pairwise distance comparisons with approximate nearest-neighbor search to avoid potentially superlinear total work.The relaxation preserves sufficient covering and packing properties while reducing the cost of constructing nets.
- Net construction: The resulting net is a δ-covering and a δ/4-packing, with size bounded by 3^d(n/m).The packing and covering properties follow from the algorithm’s removal and selection rules.
- Distance-preserving partition: The partition bounds cluster diameter by 4δ and splits any pair of points with probability O(d) · ρ(x, y)/δ.This probabilistic separation property supports distance preservation across the hierarchy.
- Distance-preserving partition: A hierarchical partition algorithm recursively partitions cells using nets and random radii, producing distance-preserving clusters in bounded-dimension metrics.The construction proceeds through L phases and uses net computation within each parent cell.
- MST algorithm: The framework computes a spanning tree whose expected cost is 1 + ϵ times the minimum spanning tree cost.The MST result is obtained for geometric metrics with bounded doubling dimension under the framework’s assumptions.
7 Lower Bounds
The section establishes conditional and oracle-model lower bounds for exact or approximate MST computation. These results connect geometric MST difficulty to sparse-graph connectivity and show that bounded dimension and approximation are important for efficient algorithms.
- Conditional lower bound: A constant-round exact MST algorithm in ℓ∞^d for d = 100 log n would yield a constant-round algorithm for connectivity in general sparse graphs.The reduction maps graph edges to points whose MST cost distinguishes connected from disconnected graphs.
- Conditional lower bound: With high probability, connected graphs produce MST cost 2(E −1), whereas disconnected graphs produce cost at least 2(E −1) + 2.The cost gap enables connectivity to be decided from the exact MST cost.
- Distance-oracle lower bounds: In the black-box distance-oracle model, exact MST requires n^2/16 distance queries and at least n^2/(16ms^2) rounds for doubling dimension at most log 3.The lower bound applies to sets with more than 6 points and success probability greater than 1/2.
- Upper-bound contrast: Under the common assumption s = n^c for constant c ∈ (0, 1), the communication lower bound becomes n^Ω(1) rounds.This follows from the sparse-regime assumption n = Θ(m·s).
- Distance-oracle lower bounds: Even a B = O(1) approximation to MST requires Ω(n^2/B) distance queries and Ω(n^2/(Bms^2)) parallel rounds in the oracle model.Thus approximation alone does not remove the need for additional structural assumptions.