Parallel algorithms for geometric graph problems
From MaRDI portal
Publication:5259593
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 -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, . We note that while recently Sharathkumar and Agarwal developed a near-linear time algorithm for -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 -approximation algorithm with space in the streaming-with-sorting model with 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.
Recommendations
- Geometric spanners in the MapReduce model
- A fast and simple algorithm for computing approximate Euclidean minimum spanning trees
- An optimal parallel algorithm for minimum spanning trees in planar graphs
- A Parallel Algorithm for Computing Minimum Spanning Trees
- Faster algorithms for the geometric transportation problem
Cites work
- scientific article; zbMATH DE number 5485440 (Why is no real title available?)
- scientific article; zbMATH DE number 5485574 (Why is no real title available?)
- Advances in Cryptology – CRYPTO 2004
- Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
- Bounds on the sample complexity for private learning and private data release
- Characterizing the sample complexity of private learners
- Collusion-secure fingerprinting for digital data
- Differential privacy and the fat-shattering dimension of linear queries
- Efficient algorithms for privately releasing marginals via convex relaxations
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- Interactive privacy via the median mechanism
- Iterative Constructions and Private Data Release
- Lower bounds in differential privacy
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- On the complexity of differentially private data release, efficient algorithms and hardness results
- On the geometry of differential privacy
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Theory of Cryptography
Cited in
(28)- Preconditioning for the Geometric Transportation Problem
- Component stability in low-space massively parallel computation
- A unified framework for clustering constrained data without locality property
- Towards optimal running timesfor optimal transport
- 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
- Brief announcement: MapReduce algorithms for massive trees
- scientific article; zbMATH DE number 7650079 (Why is no real title available?)
- Equivalence classes and conditional hardness in massively parallel computations
- A data-dependent approach for high-dimensional (robust) Wasserstein alignment
- Distributed-prover interactive proofs
- The hardness of optimization problems on the weighted massively parallel computation model
- Large-scale distributed algorithms for facility location with outliers
- Maliciously secure massively parallel computation for all-but-one corruptions
- Geometric spanners in the MapReduce model
- Distributed algorithms for matching in hypergraphs
- Streaming Euclidean MST to a constant factor
- FPTAS for minimizing the earth mover's distance under rigid transformations and related problems
- scientific article; zbMATH DE number 7561507 (Why is no real title available?)
- Round compression for parallel matching algorithms
- On geometric prototype and applications
- Density-based clustering in MapReduce with guarantees on parallel time, space, and solution quality
- scientific article; zbMATH DE number 437554 (Why is no real title available?)
- scientific article; zbMATH DE number 7525452 (Why is no real title available?)
- scientific article; zbMATH DE number 3980549 (Why is no real title available?)
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)
