Parallel algorithms for geometric graph problems

DOI10.1145/2591796.2591805zbMATH Open1315.05133arXiv1401.0042OpenAlexW2057082426MaRDI QIDQ5259593FDOQ5259593

Alexandr Andoni, Grigory Yaroslavtsev, Aleksandar Nikolov, Krzysztof Onak

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Abstract: 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+epsilon)$-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_{e}psilon(1)}$. We note that while recently Sharathkumar and Agarwal developed a near-linear time algorithm for $(1+epsilon)$-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+epsilon)$-approximation algorithm with $n^{delta}$ space in the streaming-with-sorting model with $1/delt{a}^{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.

Full work available at URL: https://arxiv.org/abs/1401.0042

zbMATH Keywords

minimum spanning treeparallel computationMapReduceearth-mover distance

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Parallel algorithms in computer science (68W10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of Cryptography
• The geometry of differential privacy: the small database and approximate cases
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster Algorithms for Privately Releasing Marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately releasing conjunctions and the statistical query barrier
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (28)

• Towards optimal running timesfor optimal transport
• A unified framework for clustering constrained data without locality property
• Efficient Algorithms for Geometric Graph Search Problems
• Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
• Neighborhood hypergraph model for topological data analysis
• Parallel strategies for geometric probing
• Parallel algorithms for shortest path problems in polygons
• Title not available (Why is that?)
• A data-dependent approach for high-dimensional (robust) Wasserstein alignment
• Distributed-prover interactive proofs
• Equivalence classes and conditional hardness in massively parallel computations
• The hardness of optimization problems on the weighted massively parallel computation model
• On Geometric Prototype and Applications
• Maliciously secure massively parallel computation for all-but-one corruptions
• Deterministic Massively Parallel Connectivity
• Distributed algorithms for matching in hypergraphs
• Streaming Euclidean MST to a constant factor
• Brief Announcement: MapReduce Algorithms for Massive Trees
• Round Compression for Parallel Matching Algorithms
• Title not available (Why is that?)
• FPTAS for minimizing the earth mover's distance under rigid transformations and related problems
• Density-based clustering in MapReduce with guarantees on parallel time, space, and solution quality
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Preconditioning for the Geometric Transportation Problem
• Component stability in low-space massively parallel computation

Uses Software

• SuLQ

This page was built for publication: Parallel algorithms for geometric graph problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259593)