Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem

DOI10.1137/16M1095482zbMath1464.68124WikidataQ126979758 ScholiaQ126979758MaRDI QIDQ4997308

Yang Li, Sepehr Assadi, Sanjeev Khanna

Publication date: 29 June 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

communication complexitystreaming algorithmsset covercovering integer programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Communication complexity, information complexity (68Q11)

Related Items (1)

Beep-and-sleep: message and energy efficient set cover

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An information statistics approach to data stream and communication complexity
• Approximation algorithms for combinatorial problems
• On graph problems in a semi-streaming model
• How to compress interactive communication
• A threshold of ln n for approximating set cover
• Constructive Proofs of Concentration Bounds
• On the hardness of approximating minimization problems
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover
• Communication Complexity
• Semi-Streaming Set Cover
• Analytical approach to parallel repetition
• Tight bounds for single-pass streaming complexity of the set cover problem
• Approximating matching size from random streams
• Elements of Information Theory

This page was built for publication: Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem