Distributed algorithms for matching in hypergraphs

DOI10.1007/978-3-030-80879-2_3MaRDI QIDQ2117684zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• A fast and simple randomized parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Algorithm for optimal winner determination in combinatorial auctions
• Approximating the k-set packing problem by local improvements
• Coalition structure generation with worst case guarantees
• Communication steps for parallel query processing
• Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
• Diverse near neighbor problem
• Faster fully dynamic matchings with small approximation ratios
• Fully Dynamic Matching in Bipartite Graphs
• Greedy local improvement and weighted set packing approximation
• scientific article; zbMATH DE number 1617260 (Why is no real title available?)
• scientific article; zbMATH DE number 7033166 (Why is no real title available?)
• scientific article; zbMATH DE number 1302177 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1064419 (Why is no real title available?)
• scientific article; zbMATH DE number 2079339 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Large neighborhood local search for the maximum set packing problem
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• On linear and semidefinite programming relaxations for hypergraph matching
• On the complexity of approximating \(k\)-set packing
• 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
• Parallel algorithms for geometric graph problems
• Perfect matchings in random s‐uniform hypergraphs
• Perfect matchings in random uniform hypergraphs
• Randomized composable core-sets for distributed submodular maximization
• Reducibility among combinatorial problems
• Round compression for parallel matching algorithms
• Sorting, searching, and simulation in the MapReduce framework
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation

Cited in

(4)

• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• scientific article; zbMATH DE number 1140608 (Why is no real title available?)
• Semi-streaming algorithms for hypergraph matching
• On the distributed complexity of the semi-matching problem

Describes a project that uses

Uses Software

• Stony Brook
• KONECT

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

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