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

DOI10.1145/2898960zbMath1445.68351arXiv1304.6906MaRDI 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 complexity; streaming algorithms; job assignment; semi-matchings

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

68M12: Network protocols

68W27: Online algorithms; streaming algorithms

68Q11: Communication complexity, information complexity