Distributed algorithms for matching in hypergraphs

DOI10.1007/978-3-030-80879-2_3OpenAlexW3185821508MaRDI QIDQ2117684

Oussama Hanguir, Clifford Stein

Publication date: 22 March 2022

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

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Uses Software

• Stony Brook
• KONECT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On linear and semidefinite programming relaxations for hypergraph matching
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• A fast and simple randomized parallel algorithm for maximal matching
• Coalition structure generation with worst case guarantees
• On the complexity of approximating \(k\)-set packing
• Greedy Local Improvement and Weighted Set Packing Approximation
• Randomized Composable Core-sets for Distributed Submodular Maximization
• Sorting, Searching, and Simulation in the MapReduce Framework
• Approximating the $$k$$-Set Packing Problem by Local Improvements
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Perfect matchings in random uniform hypergraphs
• Faster Fully Dynamic Matchings with Small Approximation Ratios
• Communication Steps for Parallel Query Processing
• Perfect matchings in random s‐uniform hypergraphs
• Reducibility among Combinatorial Problems
• Diverse near neighbor problem
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• Round compression for parallel matching algorithms
• Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
• Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
• Parallel algorithms for geometric graph problems
• Large Neighborhood Local Search for the Maximum Set Packing Problem
• Fully Dynamic Matching in Bipartite Graphs
• Algorithm for optimal winner determination in combinatorial auctions

This page was built for publication: Distributed algorithms for matching in hypergraphs