Approximating Semi-matchings in Streaming and in Two-Party Communication

DOI10.1145/2898960zbMath1445.68351arXiv1304.6906OpenAlexW1831744648MaRDI QIDQ4962609

Adi Rosén, Christian Konrad

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms, Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

communication complexitystreaming algorithmsjob assignmentsemi-matchings

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Network protocols (68M12) Online algorithms; streaming algorithms (68W27) Communication complexity, information complexity (68Q11)

Related Items (4)

The Densest $k$-Subhypergraph Problem ⋮ On computing an optimal semi-matching ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams

This page was built for publication: Approximating Semi-matchings in Streaming and in Two-Party Communication